LeetCode162 Find Peak Element

Posted on In

题目描述

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

1
2
3
4
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Your solution should be in logarithmic complexity.

解析

题意十分简短，也很好理解，就是一个数组，找出比左右大的那个数的index，其中最左边和最右边默认都是-∞，一个很直观的思路就扫描一遍，挨个比较左右，时间复杂度为O（n）, 但是题目后面还有一个要求，时间复杂度要为O(logn)。

显然遇到数组这类题目，O(logn)一个很直观的思路就是二分，不过二分是基于排序好的数组，那这个题目如何二分呢？

其实注意到num[i] 与 num[i+1]的关系是解决本题的关键，引用下Leetcode解题区的图，这个问题可以分为下面三种情况讨论:

我们发现peak是一个分界点，在这个分界点左边为上升区间，在这个分界点右边为下降区间，这样二分的思路就变得清晰了起来:

每次二分取mid，如果我们发现nums[mid] > nums[mid+1]，说明这个mid位于一个下降的区间，peak应该出现在mid左边，则搜算范围应该是[left, mid]
如果nums[mid] < nums[mid+1]，则说明mid是在一个上升的区间上，搜索范围则应该是[mid+1, right]
注意到题目中说明元素各不相同，我们不需要考虑相等的情况
代码如下：

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

总结

这是一道挺经典的二分变种，考察对二分搜索的认识和灵活使用，问题关键在于发现peak是上升区间和下降区间的分界点利用这个性质来进行二分搜索，挺适合作为面试题来出的，如果我是考官的话:)