题解 | 寻找峰值

#include <limits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        int len = nums.size();
        int lh = 0, rh = len, mid; // range [lh, rh)
        int lnb, rnb;
        while(true) {
            mid = (lh + rh) / 2;
            lnb = mid == 0 ? numeric_limits<int>::min() : nums[mid - 1];
            rnb = mid == len - 1 ? numeric_limits<int>::min() : nums[mid + 1];
            if(lnb < nums[mid] && rnb < nums[mid]) {
                return mid;
            } else if(lnb < nums[mid] && rnb >= nums[mid]) {
                lh = mid + 1;
            } else if(lnb >= nums[mid] && rnb < nums[mid]) {
                rh = mid;
            } else {
                // valley, both direction is ok
                lh = mid + 1;
            }
        }
        // NEVER REACHED HERE!
        return -1;
    }
};

看到时间复杂度O(logN)，想到二分查找，先套模板再说，与二分查找不同的是需要check一下两边的变化方式，共四种情况，如果刚好遍历到谷值，两个方向都可以查找