题解 | #寻找峰值#

没想到能一遍过😋记录一下思路：

1. 首先想到是用一个大小为3的窗口遍历数组，一步步检查中间的元素是否为峰值。但发现题目要求时间复杂度为logn，而且数据长度范围太长了，果断放弃。
2. 第二个想法是用两个指针，分别从左向右和从右向左遍历两遍，分别记录上升的序列位置，相交的位置就是峰值。中间还想过只从前往后遍历一遍并记录由上升到下降的转折点，但很显然都会超时。不过这也给了我一点提示，即我们想寻找峰值，肯定是更加关注那些上升的区间，于是第三个想法油然而生。
3. 这题最关键的地方在于，题干中明确了相邻值不相等。乍一看，这只与判断峰值时是否有等于号有关，其实不然。更重要的一点是，这决定了，一旦一个区间内数值在上升，则必然有一个峰值！于是我们可以沿着这个思路，即沿着某一个上升区间走，最终必然能找到一个峰值。
4. 由于时间复杂度要求为logn，沿着上升区间一步步遍历肯定不行，于是很自然地想到了二分法。先看[head，tail]区间中点是否为峰值，如果不是的话就判断以这个中点为起点向右是否为上升趋势，如果是就再用同样的方法在[中点+1，tail]区间内查找，如果不是就在[head，中点-1]区间找。如此循环，我们就能找到其中一个峰值，题目也只要求找到一个峰值即可。

代码看起来还是很简单的，有趣的还是这个思路🙂

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    bool isPeak(vector<int>& nums, int index) {
        if (index == 0) return nums[index] > nums[index + 1];
        else if (index == nums.size() - 1) return nums[index] > nums[index - 1];
        else return nums[index] > nums[index - 1] && nums[index] > nums[index + 1];
    }
    bool whichDirection(vector<int>& nums, int index) {
        // 选择往哪个方向，1为右，0为左
        if (index == 0)return 1;
        else if (index == nums.size() - 1) return 0;
        else return nums[index + 1] > nums[index];
    }
    int findPeakElement(vector<int>& nums) {
        // write code here
        int length = nums.size();
        int index = length / 2;
        int head = 0, tail = length - 1;
        while (1) {
            if (isPeak(nums, index)) return index;
            if (whichDirection(nums, index)) head = index + 1;
            else tail = index - 1;
            index = (tail - head + 1) / 2 + head;
        }
    }
};