leetcode-852 Peak Index in a Mountain Array

852. Peak Index in a Mountain Array

Description

Let’s call an array A a mountain if the following properties hold:

  • A.length >= 3
  • There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
  • Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

1
2
Input: [0,1,0]
Output: 1

Example 2:

1
2
Input: [0,2,1,0]
Output: 1

Note:

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A is a mountain, as defined above.

Analyse

简单题，就理解成找最大值的index
Moutain都是先上后下的一个形状，对下降的那个节点做判断就能得出结果

算法复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
int peakIndexInMountainArray(vector<int>& A) {
    int i = 1;
    while (i <= A.size())
    {
        if (A.at(i-1) > A.at(i))
        {
            return i-1;
        }
        ++i;
    }
}

这样提交上去的结果不是很好，做一些修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int x=[](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        for (int i = 1; i <= A.size(); i++)
        {
            if (A.at(i-1) > A.at(i))
            {
                return i-1;
            }
        }
    }
};

还可以直接找最大值的index，甚至都不用自己写，直接调函数，这样就beat 100.00%了

1
2
3
4
5
int peakIndexInMountainArray(vector<int>& A)
{
    vector<int>::iterator max_iter = max_element(A.begin(), A.end());
    return distance(A.begin(), max_iter);
}