描述

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1. 峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2. 假设 nums[-1] = nums[n] = Integer.MIN_VALUE
3. 对于所有有效的 i 都有 nums[i] != nums[i + 1]

数据范围：

1. 1<n<=2x10^5
2. -2^31<=nums[i]<=2^31-1

思路1：寻找最大值

省略

思路2：遍历左右比较

思路1和思路2，最差的情况坡峰在最后一个值，时间复杂度为O(n)

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

思路3：二分法

下坡不一定有坡峰，上坡一定有坡峰，不断压缩区间。时间复杂度为O(logn)

public class Solution {
    public int findPeakElement (int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        while(i < j) {
            int mid = i + (j - i >> 1);
            if(nums[mid] < nums[mid + 1]) {
                //mid小于mid+1，说明mid不可能是坡峰，可以跳过
                i = mid + 1;
            } else {
                //mid>=mid+1，mid有可能是坡峰，不能跳过
                j = mid;
            }
        }
        return i;
    }
}