Leetcode162. 寻找峰值

题目描述

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

示例 1：

1
2
3
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

1
2
3
4
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

  • 1≤nums.length≤10001 \leq nums.length \leq 1000​
  • −231≤nums[i]≤231−1-2^{31} \leq nums[i] \leq 2^{31} - 1​
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

**进阶：**你可以实现时间复杂度为 O(logN) 的解决方案吗？

解题思路

这道题最简单的方法就是线性扫描，但是简单题当面试题，那就必须找到最优解法。这道题最优解法是二分法。

一般情况下，二分法的使用必须满足有序的条件，这道题中的数组整体看并不是有序的，但是满足局部有序的条件。因为事先假定有峰顶元素，并且只需要返回其中一个峰顶元素的下标，因此我们可以尝试用二分法去解决这道题。

具体的思路如下：

首先从数组 nums 中找到中间的元素 mid。若该元素恰好位于降序序列或者一个局部下降坡度中（通过将 nums[mid] 与右侧比较判断)，则说明峰值会在本元素的左边。于是，我们将搜索空间缩小为 mid 的左边(包括其本身)，并在左侧子数组上重复上述过程。

若该元素恰好位于升序序列或者一个局部上升坡度中（通过将 nums[mid] 与右侧比较判断)，则说明峰值会在本元素的右边。于是，我们将搜索空间缩小为 mid 的右边，并在右侧子数组上重复上述过程。

就这样，我们不断地缩小搜索空间，直到搜索空间中只有一个元素，该元素即为峰值元素。

但是，需要强调的一点是，这道题使用二分法的条件是：事先假定一定存在峰顶元素，并且只需要返回其中一个峰顶元素的下标。

参考代码

二分法的实现有迭代和递归两种，由于迭代法的空间复杂度更优，所以直接用迭代法实现。

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

复杂度分析

时间复杂度：O(log(n))O(log(n))​

空间复杂度：O(1)O(1)​