0162. 寻找峰值 #

• 标签：数组、二分查找
• 难度：中等

题目大意 #

给定一个整数数组 nums。

要求：找到峰值元素并返回其索引。必须实现时间复杂度为 O(log n) 的算法来解决此问题。

• 峰值元素：指其值严格大于左右相邻值的元素。

注意：

• 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
• 可以假设 nums[-1] = nums[n] = -∞。

解题思路 #

可以使用二分查找来查找峰值。

• 使用两个指针 left、right 。left 指向数组第一个元素，right 指向数组最后一个元素。
• 取区间中间节点 mid，并比较 nums[mid] 和 nums[mid + 1] 的值大小。
  • 如果 nums[mid] 小于 nums[mid + 1]，则右侧存在峰值，令 left = mid + 1。
  • 如果 nums[mid] 大于等于 nums[mid + 1]，则左侧存在峰值，令 right = mid。
• 最后，当 left == right 时，跳出循环，返回 left。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left