LeetCode 162. Find Peak Element

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 162. Find Peak Element 原题链接中等

作者：

yxc , 2018-06-01 23:59:18 , 所有人可见 , 阅读 4622

16

17

题目描述

峰值定义为比左右相邻元素大的元素。

给定一个数组 nums，保证 nums[i] ≠ nums[i+1]，请找出该数组的峰值，并返回峰值的下标。

数组中可能包含多个峰值，只需返回任意一个即可。

假定 nums[-1] = nums[n] = -∞。

样例1

输入：nums = [1,2,3,1]
输出：2
解释：3是一个峰值，3的下标是2。

样例2

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：数组中有两个峰值：1或者5，返回任意一个即可。

算法

(二分) $O(logn)$

仔细分析我们会发现：

如果 nums[i-1] < nums[i]，则如果 nums[i-1], nums[i], ... nums[n-1] 是单调的，则 nums[n-1]就是峰值；如果nums[i-1], nums[i], ... nums[n-1]不是单调的，则从 $i$ 开始，第一个满足 nums[i] > nums[i+1]的 $i$ 就是峰值；所以 $[i,n-1]$ 中一定包含一个峰值；
如果 nums[i-1] > nums[i]，同理可得 $[0, i-1]$ 中一定包含一个峰值；

所以我们可以每次二分中点，通过判断 nums[i-1] 和 nums[i] 的大小关系，可以判断左右两边哪边一定有峰值，从而可以将检索区间缩小一半。

时间复杂度分析：二分检索，每次删掉一半元素，所以时间复杂度是 $O(logn)$。

C++ 代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        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 r;
    }
};

20 评论

fightsuccess 3个月前

我记得有两个二分法的模板，一个是设置mid=(l + r) / 2,边界条件是r = mid,l=mid+1。另一个是mid=(l+r)/2+1,边界条件是l=mid,r=mid - 1，但这道题只有其中一个模板能得出答案，同理875，也是只有一个模板能得出答案。那到底什么时候选第一个模板，什么时候选第二个模板呢

Muzi 2023-03-22 21:52

原题里面提到了对于所有有效的 i 都有 nums[i] != nums[i + 1]，也就是说对相邻的元素a b，要么a>b，要么a<b。

从中点考虑，如果num[mid] < num[mid+1]，那我们想要的答案绝对在后半段有（后半段只有两种情况，1. num[mid+1] < num[mid+2]，这种情况num[mid+1]就是答案；2. num[mid+1] > num[mid+2]，如果后续一直增加，那符合要求的数肯定是最后一个，如果不是一直递增，那答案点一定是从增到减的那个拐点，把所有的点描出来看一下应该很直观），所以直接撇掉前半段。

如果num[mid] > num[mid+1] ,就相当于镜像一下嘛，（1.num[mid-1] < num[mid]，那num[mid]就是答案，2.num[mid-1] > num[mid]，如果从mid-1往前走一直递增，那答案就是最前面那个，如果不是一直递增，答案还是从增到减的那个拐点）前半段里面必有答案，撇掉后半段。

虽说不是和上课那种严格地左边满足某种性质，右边不满足某种性质，（或左边不满足某种性质，右边满足某种性质），但我们已经能通过分析直接分析出来左边（或右边）肯定有答案了，那就直接把右边（或左边）砍了就行了。

这道题我感觉确实挺开阔思路的，学y总的课之前我一直以为二分只能在单调的情况用，听课之后理解了在左(右)满足某种性质的时候也能用(现在想想满足性质也是为了定位答案到底在做还是右)，再到这个题，已经能直接分析出答案在哪边了那还找什么性质啊:D

tomousw 2023-02-15 19:03

### 这样写也能过

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(nums[mid]>nums[mid-1])l=mid;
            else r=mid-1;
        }
        return l;
    }
};

tomousw 2023-02-15 19:06

#### 感觉这个题在二分里挺特殊的，靠分析题目得出的二分代码，神奇的是和yls的二分板子恰好相同

DayGtightCompartment 2023-04-23 21:09 回复了 tomousw 的评论

<= nuns[mid-1] 的最后一个数，好像也说的通，斜坡上的最大值

GT 2022-05-29 02:55

y总，这道题算不算二分里面的特例？因为你之前讲二分的时候是定义一个性质使得左边和右边一个满足一个不满足这个性质进而二分找出边界。但是这个题我们我们存在多个满足条件的边界（多个peak），所以并不能想到用常规的二分法做。只能是提前知道了题目可以使用二分法，才去从中点入手考虑怎样缩小搜索范围。我感觉如果是第一次见到这个题会很难做出来。