162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

二分

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;

        // 当 left < right 时循环。这里为什么用小于而不是小于等于？因为mid最多取n-2，这样mid+1不会越界。
        // 这样会不会漏掉答案为n-1的情况？不会，因为如果答案是n-1，则left会一直右移，最终移到n-2，此时计算出mid=n-2，
        // 比较发现nums[n-2]<=nums[n-1]，所以。left继续右移，到n-1，退出循环，返回n-1.
        while (left < right) {
            int mid = (left + right) / 2;

            // 比较 mid 和 mid + 1 的值，判断峰值在左侧还是右侧
            if (nums[mid] > nums[mid + 1]) {
                // 峰值在左侧，包括 mid
                right = mid;
            } else {
                // 峰值在右侧，不包括 mid
                left = mid + 1;
            }
        }

        // 当 left == right 时，返回峰值的索引
        return left;
    }
}

想用 left <= right 的话，请看下面的代码。或许比上面的代码更好理解。

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;

        while (left <= right) { // 使用 left <= right 作为循环条件
            int mid = (left + right) / 2;

            // 判断是否满足峰值条件。重点。
            if ((mid == 0 || nums[mid] > nums[mid - 1]) && 
                (mid == n - 1 || nums[mid] > nums[mid + 1])) {
                return mid;
            }
            // 不满足峰值条件时只有小于右边元素和大于右边元素之分，即只有下面两种情况。
            // 题目说不存在等于的情况。重点。
            // 如果 mid 的右边元素较大，说明峰值在mid右侧。
            else if (mid < n - 1 && nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            }
            // 否则，峰值在左侧。不可能在mid处，因为上面已经确保此处的mid不是峰值。
            // 注意mid一定大于等于0，所以直接用else即可
            else {
                right = mid - 1;
            }
        }

        // 理论上不会执行到这里，因为循环中会返回峰值索引
        return -1;
    }
}

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$