题解 | #寻找峰值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */

    int findPeakElement(vector<int>& nums) {
        // write code here
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int left = (mid == 0) ? INT_MIN : nums[mid - 1];     
            int right = (mid == nums.size() - 1) ? INT_MIN : nums[mid + 1];  
            if(left < nums[mid] && nums[mid] > right){
                return mid;
            }
            else if(left < nums[mid]){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }

        return l;
    }
};

每次查找有四种情况：

上坡：nums[mid - 1] < nums[mid] < nums[mid + 1]

下坡：nums[mid - 1] > nums[mid] > nums[mid + 1]

峰顶: nums[mid - 1] < nums[mid]，nums[mid] > nums[mid + 1]

峰谷: nums[mid - 1] > nums[mid]， nums[mid] < nums[mid + 1]

其中除了峰顶以外其他都不是我们想要的。

可以选确定是不是峰顶，不是峰顶，那只能在峰顶的上坡或者下坡，如果是上坡左边界就得收缩，反之在下坡右边界就得收缩。