问题

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。你的解法应该是 O(logN) 时间复杂度的。

示例

输入:nums = [1,2,3,1] 输出:2

输入:nums = [1,2,1,3,5,6,4] 输出:15

思路

如果没有特殊要求,直接扫描数组即可,但是题目要求时间复杂度为O(logN),这样的话就需要采用二分查找的方法来处理了。首先需要确定缩小边界的方法,这里根据题意可以知道,当nums[mid] > nums[mid + 1]时,峰值会在区间的左边,此时缩小右区间且不舍弃mid。反之,则缩小左区间。应该注意到的是,这里比较的是nums[mid]和nums[mid + 1],循环的终止条件应该为left < right

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}