leetcode：162. 寻找峰值

题目来源

• leetcode：162. 寻找峰值

题目描述

class Solution {
    
public:
    int findPeakElement(vector<int>& nums) {
    

    }
};

题目解析

分析题意

• 首先要注意题目条件，在题目描述中出现了 nums[-1] = nums[n] = -∞，这就代表着只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值
  

• 因为数组中的峰值不止一个，我们找到任意一个即可。

• 题目还告诉我们对于所有有效的i都有 nums[i] != nums[i + 1]，即数组中的任意两个相邻数都不相等。

思路

• 我们使用二分来做，每次找出区间的中点mid，比较nums[mid]与nums[mid + 1]的大小关系来推断哪个区间内一定存在峰值，然后取一定存在峰值的区间。这样不断缩小区间范围，区间所剩下的最后一个数就是答案。

过程

• 二分的边界： l = 0, r = nums.size() - 1
• 如果nums[mid] > nums[mid + 1]，那么在[l, mid]这个区间内一定存在一个峰值。因为[l,mid]这一段如果是单调递减的话，那么nums[l]就是峰值，否则第一个出现上升的点就是峰值。

• 如果nums[mid] < nums[mid + 1]，那么在[mid+1, r]这个区间内一定存在一个峰值。因为[mid+1,r]这一段如果是单调递增的话，那么nums[r]就是峰值，否则第一个出现下降的点就是峰值。

class Solution {
    
public:
    int findPeakElement(vector<int>& nums) {
    
        int N = nums.size();


        int L = 0, R = N - 1;
        while (L < R){
    
            int mid = L + (R - L) / 2;
            if(nums[mid] > nums[mid + 1]){
    
                R = mid;
            }else{
    
                L = mid + 1;
            }
        }
        return R;
    }
};