跳转至

LeetCode: 162. 寻找峰值

1、题目描述

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

说明:

你的解法应该是 O(logN) 时间复杂度的。

2、解题思路

​ 直接找最大值,返回索引

class Solution:
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return nums.index(max(nums))

​ 刚刚找最大值,是一个取巧的方式,可以使用递归来做,首选进行二分,然后在如果中间值不是,就在左面和右面寻找

​ 如果找到一个,就返回

使用二分法来做,进行空间的缩小

  • 如果中间节点位于上升序列,我们认为右面还有一个下降序列,峰值在右面
  • 如果中间节点位于下降序列,那么在左面就还有一个上升序列,峰值在左面
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1

        return left