162. Find Peak Element

发表于 | 分类于 | 浏览 次

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] = -∞.

Example 1:

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.

Example 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.

Note:

Your solution should be in logarithmic complexity.

解法1：线性扫描

依次检查每一个元素nums[i]是否大于它的下一个元素nums[i+1]，当我们开始比较nums[i]和nums[i+1]的大小时，我们已知知道nums[i-1]和nums[i]之间的大小关系是nums[i] > nums[i-1]。

这个问题可以分为三种可能的情况，其余情况都是这三种情况的组合。

  1. 整个数组是单调递减的。
  2. 整个数组是单调递增的。
  3. 整个数组先递增后递减，即peak num出现在中间位置。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for(int i=0;i<nums.size()-1;++i){
            if(nums[i] > nums[i+1]){
                return i;
            }
        }
        return nums.size()-1;
    }
};

解法2：递归二分查找

在简单的二分查找中，我们在一个有序数组中每一步减少搜索空间来找出满足条件的元素。同样，在这里也可以利用二叉查找来找到peak num。
在[lo, hi]给定的区间内，首先检查第mid个元素(mid = (lo + hi) / 2)，如果nums[mid]属于递减子数组，那么peak num只能出现在[lo, mid]中，否则，peak num只能出现在[mid+1, hi]中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.empty()){
            return -1;
        }
        return search(nums, 0, nums.size()-1);
    }
    int search(vector<int>& nums, int lo, int hi){
        if(lo == hi){
            return hi;
        }
        int mid = (lo + hi) >> 1;
        if(nums[mid] > nums[mid + 1]){
            return search(nums, lo, mid);
        }
        return search(nums, mid + 1, hi);
    }
};

时间按复杂度：O(log(n))
空间复杂度：O(log(n))

解法3：迭代二叉查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.empty()){
            return -1;
        }
        int l = 0, r = nums.size()-1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] > nums[mid+1]){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
};