Cinte's Leetcode Record
0%

162. 寻找峰值

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

162. 寻找峰值

同852. 山脉数组的峰顶索引

同剑指 Offer II 069. 山峰数组的顶部

O(n)时间复杂度，简单的遍历

当全都升序的时候。只有最后一个元素是山峰。没有符合nums[i] > nums[i + 1]的

当全都降序的时候。第一个元素是山峰，直接返回。第一个元素符合nums[i] > nums[i + 1]，后面的符合但是不是解，但是由于已经直接返回了，所以不会影响结果。

当中间有转折的时候。nums[i] > nums[i + 1]必定是符合的。

存不存在符合nums[i] > nums[i + 1]但是不是山峰的情况呢？只在全都降序时候第一个元素之后的存在。而这种情况上面说了对结果没有影响。总而言之就是只需要判断nums[i] > nums[i + 1]就可以了。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for(int i = 0, sz = nums.size(); i < sz - 1; ++i)
            if(nums[i] > nums[i + 1])
                return i;
        return nums.size() - 1;
    }
};
O(logn)二分查找

当nums[mid] > nums[mid + 1]时

这时候他处于一个递减子序列中，那么他的左边必定存在一个山峰，即使左边全是递减的，那么结果也会是左边的第一个元素。

如果他处于一个递增子序列，那么山峰一定会在他的右边。

如果恰好是lo和hi中间一块为单调，但lo和hi又不等于开头和结尾。

假设中间一块单调增加，如果之前的hi要到现在的hi，必定在那里存在一个山峰。

如果中间一块单调减少，如果之前的lo要到现在的lo，必定也在那里存在一个山峰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = lo + (hi - lo) / 2;
            // mid总是像左边靠，所以不会存在mid+1越界的情况，当只有一个元素时候，循环已经退出。
            if(nums[mid] > nums[mid + 1])
                hi = mid;
            else
                lo = mid + 1;
        }
        return hi;
    }
};