162. 寻找峰值

题目链接：

法一、暴力 \(O(n)\)

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0;
        if (n == 2) {
            if (nums[0] < nums[1]) return 1;
            else if (nums[0] > nums[1]) return 0;
        }
        for (int i = 0; i < n; i++) {
            if (nums[0] > nums[1]) return 0;
            if (nums[n - 2] < nums[n - 1]) return n - 1;
            if (i > 0 && i < n - 1 && nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
        }
        return 0;
    }
};

法二、二分

（数组不有序也可二分）

题目保证峰顶一定存在，且在 \(i<n-1\) 时，若有 \(\rm nums[i] < nums[i+1]\)，则在 \(\rm [i+1,n-1]\) 必有峰顶存在。
同理，若 \(\rm nums[i] > nums[i+1]\)，则在 \(\rm [0,i]\) 必有峰顶存在。

证明过程：

即峰顶及右侧为 \(\rm true\)，峰顶左侧为 \(\rm false\)

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 >> 1;
            if (nums[mid] < nums[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};