【leetcode】852 Peak Index in a Mountain Array

发表于

描述
求一个有峰值的序列的峰值

思路
很简单的一道题，但是考验一点点思维和仔细。我直接找最大值了，算法效率是O(N)。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int max_val = A[0];
        int ind = 0;
        for (int i = 1; i < A.size(); i++) {
            if(max_val<A[i]){
                max_val = A[i];
                ind = i;
            }
        }
        return ind;
    }
};

大佬代码
大佬采用了二分查找，时间复杂度为O(log2(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int len = A.size();
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] < A[mid + 1]) { left = mid + 1; }
            else { right = mid; }
        }
        return left;
    }
};

另外，这道题其实不是找最大值，而是找峰值，于是这样也可以解决，时间负责度为O(N)

1
2
3
4
5
6
7
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int i = 0;
        while (A[i] < A[i+1]) i++;
        return i;
    }
}

参考链接
原题链接