0162. 寻找峰值

0162. 寻找峰值 #

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

题目大意 #

给定一个整数数组 nums

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

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

注意:

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

解题思路 #

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

  • 使用两个指针 leftrightleft 指向数组第一个元素,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
本站总访问量  次  |  您是本站第  位访问者