LeetCode 162. 寻找峰值

线性扫描

初始条件：

• nums[-1] = nums[n] = -∞
• nums[i] != nums[i + 1]

情况1：所有数字降序排列。检查当前元素是否大于下一元素，第一个元素即满足条件，为峰值。
情况2：所有数字升序排列。检查当前元素是否大于下一元素，没有元素符合条件，直到末尾，末尾元素为峰值。
情况3：峰值出现在中间某处。满足当前元素大于下一元素的即为峰值。

class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) return i;
        }
        return nums.length - 1;
    }
}

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

二分法

若该元素恰好位于降序序列或者一个局部下降坡度中（nums[mid] > nums[mid + 1])，则说明峰值会在左边。
若该元素恰好位于升序序列或者一个局部上升坡度中（nums[mid] > nums[mid + 1])，则说明峰值会在右边。

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

• 时间复杂度：O(logn)
• 空间复杂度：O(1)