寻找峰值

寻找峰值_牛客题霸_牛客网

问题简述

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = -inf
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

进阶：时间复杂度 O(logN)

思路1：遍历

• 注意问题中假设左右边界为负无穷，因此当数组中只有一个或两个元素时也是存在答案的；

Python

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        
        nums = nums + [float('-inf')]
        pre = float('-inf')
        for i in range(len(nums)):
            if nums[i] > pre:
                mx_i = i
            if nums[i] < pre:
                return mx_i
            pre = nums[i]

思路2：找最大值

• 根据问题定义，最大值必定是答案之一

Python

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        
        return nums.index(max(nums))

思路3：二分（最佳）

• 可以通过比较 nums[m] 和 nums[m + 1] 可以确定所在位置是“上坡”还是“下坡”；

• 注意：二分有效的前提是 对于所有有效的 i 都有 nums[i] != nums[i + 1]；

Python

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] < nums[m + 1]:  # 上坡；因为 l < r，所以 m+1 不会越界
                l = m + 1
            else:  # 下坡
                r = m 
                if m == 0 or nums[m - 1] < nums[m]:  # 这段去掉也能 AC
                    return m
        
        return l