题解 | #寻找峰值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        // write code here
        //只要向高的地方收缩一定可以找到一个峰值
        int left=0;
        int right=nums.size()-1;
        
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[mid+1])//左边一定有峰值,并且可能是mid
            {
                right=mid;
            }
            else 
            {
                left=mid+1;
            }
        }

        return right;
    }
};

1.思路：对于一个数组，如果认为它的两端（下标为-1，size（）两处）是最低的，那么这个数组一定存在峰值；因此nums一定存在峰值。

取nums的中点下标mid,如果nums[mid]>nums[mid+1],那么mid的左区域（含mid)一定存在峰值（因为左区域两端是最低的）将

这个区域作为新的"nums数组";如果nums[mid]<nums[mid+1],那么mid的右区域（不含mid)一定存在峰值（因为右区域两端是最低的）将这个区域作为新的"nums数组"执行算法，这样"nums数组"就会向存在峰值的方向不断缩小，直到可以选出峰值

2.为什么返回right:

在跳出循环前的最后一步，left和right可能满足关系left+1=right或者left+2=right，

先分析left+1=right的情况

若left+1=right，计算可得：mid=left;

而我们知道峰值一定是nums[left]和nums[right]中的较大者，

假设nums[left]较大，那么，区间向左收缩，right=mid=left=峰值下标,此时返回right;

假设nums[left]较小，那么，区间向右收缩，right不变,此时返回right也是可以的;

left+2=right时

mid=left+1;

若nums[mid]<nums[right];那么，区间向右收缩，right不变,此时返回right也是可以的;

若nums[mid]>nums[right];，区间向左收缩,归结为情况left+1=right；

即：从最后一步分析可以看出，在right=left时退出循环是合理的，可以直接返回right（或者是left)