我要招人

去企业版

首页 > 试题广场 >

寻找峰值

[编程题]寻找峰值

热度指数：162827 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = $-\infty$

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

$1 \le nums.length \le 2\times 10^5 \$

$-2^{31}<= nums[i] <= 2^{31} - 1$

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

示例1

输入

[2,4,1,2,7,8,4]

输出

说明

4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2

输入

[1,2,3,1]

输出

说明

3 是峰值元素，返回其索引 2

算法知识视频讲解

牛客题解官

发表于 2022-04-22 11:40:36

精华题解题目主要信息: 给定一个长度为n的数组，返回其中任何一个峰值的索引峰值元素是指其值严格大于左右相邻值的元素数组两个边界可以看成是最小，nums[−1]=nums[n]=−∞nums[-1] = nums[n] = -\inftynums[−1]=nums[n]=−∞ 峰值不存在平的情况，即相邻展开全文

罅隙·

发表于 2022-02-04 13:05:22

思路为什么想到二分查找？因为二分查找的本质是二段性，二分查找的过程本质是对可行区间的压缩。只要满足二段性的问题都可以用二分查找解决。在这里二段性的体现是峰值的左边单调增，右边单调减。你可能会反驳给我们的数值不只有一个峰值，但是只要我们控制好条件，一定可以把范围压缩到只有一个峰值的情况，来看看展开全文

好好刷题进大厂

发表于 2021-11-24 12:23:44

1、二分法：时间复杂度o(logn),空间复杂度o(1) 思想:上坡一定有波峰，下坡不一定有波峰 import java.util.*; public class Solution { /* 展开全文

难道天要亡我？

发表于 2021-10-24 00:01:33

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * 展开全文

Flipped-tech

发表于 2022-02-28 14:30:23

根据提议感觉找最大值即可. public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @retu 展开全文

不经历怎么能成长

发表于 2022-02-23 17:42:26

分析：最简单的是循环遍历O(n) 二分查找，O(log2n) 最左边和最右边为无穷小，当任意一个位置i上的值小于相邻i+1时，则左边必然存在峰值。当任意一个位置i上的值大于相邻i+1时，右边必存在峰值。 class Solution { public: // 左右边为无穷小，所以当前位展开全文

萨根的喷火龙

发表于 2021-10-21 18:56:22

就是一层遍历，然后找到一个元素大于前面和后面的数字，然后返回下标；这里主要是注意，它的峰值可能出现在开头和结尾，需要单独提出来。 class Solution: def findPeakElement(self , nums: List[int]) -> int: # 展开全文

机智の小盆友

发表于 2022-04-12 10:06:30

首先题意比较坑，比较模糊，未说明数组长度为1，为2，还有单边递增递减这种情况怎么处理，只能通过自己提交提示错误处理思路：先排除数组长度为1，为2 这种情况长度大于等于3后，从索引1处开始遍历，取索引-1 ，索引+1 与当前比较，都比当前小，返回否则，就是单调递增或者递减，判断首节点与尾节展开全文

陈橙朱

发表于 2022-04-05 17:34:00

// 时间复杂度o(logn),空间复杂度o(1) // 思想:上坡一定有波峰，下坡不一定有波峰，但是可能找不到，一直向下走的。 // 因为，nums[-1] = nums[n] = -∞ // 最左边和最右边为无穷小，当任意一个位置i上的值小于相邻i+1时，则左边必然存在峰值 function f 展开全文

梦会绽放

发表于 2022-02-10 20:03:48

从此题中得到的小感悟：充分把握题意方能选用更合适的解题方法（类二分法）此题难度中等，很容易想到思路1，但是仅此的话，不符合“中等”的标签；另外，题中要求时间复杂度为 O(log n)，这让我们很自然地联想到二分法，我们所熟悉的二分法是基于有序表，这道题目数组并不一定有序，那又如何和二分法产生关展开全文

zanejins

发表于 2022-03-10 08:54:24

寻找峰值： 1. 如果出现上坡，则一定有峰值，在右边即if(num[mid]<nums[mid+1]) l=mid+1; 2. 如果是下坡，则峰值在左边即 r=mid; class Solution { publ 展开全文

问题信息

数组查找

上传者：牛客301499号

难度：

191条回答 931收藏 5677浏览

通过挑战的用户

查看代码

机电824

2023-02-17 16:36:20
myweek

2023-02-07 20:36:06
第四单元123

2023-01-30 16:49:15
牛客89411...

2022-12-07 22:00:57
牛客89418...

2022-10-27 15:04:05

寻找峰值

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题