数组中寻找峰值

162. 寻找峰值

描述

峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。 你可以假设 nums[-1] = nums[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, 2, 3, 4, 5, 3, 2, 1]

1. 如果 middle - 1 < middle < middle + 1 : 那么 middle 现在是处于上升区间，峰值应该在 middle 的右边
2. 如果 middle - 1 > middle > middle + 1 : 那么 middle 现在处于下降区间，峰值在 middle 左边
3. 如果 middle - 1 > middle, middle < middle + 1 : 说明 middle 正处于一个波谷，峰值在它左右都会有出现
4. 如果 middle - 1 < middle, middle > middle + 1 : 说明 middle 就是一个峰值 代码如下：

public int findPeakElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int left = 0; int right = nums.length - 1;
    while (left + 1 < right) {
        int middle = left + (right - left) / 2;
        int middleLeft = (middle - 1) > 0 ? middle - 1 : 0;
        int middleRight = (middle + 1) >= nums.length ? nums.length : middle + 1;
        // 1 < 2 < 3 峰值在 middle 右边
        if (nums[middleLeft] < nums[middle]  && nums[middle] <nums[middleRight]) {
            left = middleRight;
        } else if (nums[middleLeft] > nums[middle] && nums[middle] > nums[middleRight]) {
            // 3 > 2 > 1 峰值在 middle 左边
            right = middleLeft;
        } else if (nums[middleLeft] > nums[middle] && nums[middleRight] > nums[middle]) {
            // 3 > 2,  2 < 4 middle 正好是个低谷
            right = middleLeft;
        } else {
            return middle;
        }
    }
    if (nums[left] < nums[right]) {
        return right;
    }
    return left;
}

162. 寻找峰值