首页 > 试题广场 >

寻找峰值

[编程题]寻找峰值
  • 热度指数：41153 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。

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


提示:
1 <= 数组长度 <= 1000
0 <= 数组元素的值 <= 1000
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

按题目要求应该输出索引最大的山峰，所以对应的输出为5。
示例1

输入

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

输出

5
示例2

输入

[3,2,1,2,1]

输出

3

说明

因有两个山峰，一个是索引为0，峰值为3的山峰，另一个是索引为3，峰值为2的山峰，按题目要求应该输出索引最大的山峰，所以对应的输出为3。
算法知识视频讲解
添加回答
Python
HHHChen77头像 HHHChen77
从后往前 比较一侧 
class Solution:
    def solve(self , a ):
        # write code here
        length = len(a)
        if length == 1:
            return 0
        # 从后往前找
        for i in range(length-1, 0, -1):
            # 判断左侧是否满足条件,右侧在前面遍历过程中已经确认过了
            if a[i-1] <= a[i]:
                return i
        # 到这个位置说明数组为降序,返回第一个索引
        return 0


发表于 2021-06-25 16:21:41 回复(3)
Python
牛客诶谁头像 牛客诶谁 
class Solution:
    def solve(self , a ):
        n = len(a)
        i = -1
        # 从后向前找，如果前一个元素小于当前元素，说明找到了
        while a[i-1] > a[i]:
            i -= 1
        return n + i
编辑于 2021-04-25 00:09:00 回复(0)
Python
spongebob7头像 spongebob7
class Solution:
    def solve(self , a ):
        # write code here
        res = 0
        minv = min(a)
        aa = []
        aa.extend(a)
        aa.insert(0, minv)
        aa.append(minv)
        for i in range(len(aa)-2,0,-1):
            if aa[i]>aa[i-1] and aa[i]>aa[i+1]:
                res = i-1
                break
        return res
发表于 2021-04-07 11:48:19 回复(0)
Python
LHC0512头像 LHC0512
这道题有个技巧，就是补充两端两个最小值，可以避免一些判断 
import sys

min_value = -sys.maxsize - 1


class Solution:
    def solve(self, a):
        arr = [min_value] + a + [min_value]
        for i in range(len(arr) - 2, -1, -1):
            if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
                return i - 1




编辑于 2021-02-22 21:15:24 回复(0)
Python
半生累头像 半生累 
#
# 寻找最后的山峰
# @param a int整型一维数组
# @return int整型
#
class Solution:
    def solve(self , a ):
        if len(a) ==0:
            return -1
        i = len(a) - 1
        while i < len(a):
            if (a[i] >= a[i-1]):
                return i
                break
            else:
                i = i - 1
通过循环反向去比较就可以了，前一个值小于后一个值就是峰值。
之前写的时候犯的错误：把值和前一个、后一个都进行比较：a[i] >= a[i-1] & a[i] >= a[i+1]，其实完全没必要。

发表于 2021-01-27 15:32:18 回复(0)
提交观点

问题信息

数组
上传者：牛客332641号
难度：
5条回答 5541浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号