[Leetcode][python]寻找峰值

怼烎@ 2022-05-16 06:09 135阅读 0赞

## 题目大意 ##

[https://leetcode-cn.com/problems/find-peak-element/description/][https_leetcode-cn.com_problems_find-peak-element_description]

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

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

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

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

## 解题思路 ##

二分查找变种

## 代码 ##

### 方法1：顺序遍历。 ###

本题的一个重要特点是，从第一个元素开始，若其大于相邻的后续元素，则第一个元素就是一个局部最大值，返回即可。若其小于相邻的后续元素，则第二个元素大于第一个元素。如此，一一遍历数组，第一次出现，第i个元素若大于其相邻后续元素，则该元素就是一个局部最大值

### 方法2：二分查找 ###

思路：如果中间元素大于其相邻后续元素，则中间元素左侧(包含该中间元素）必包含一个局部最大值。如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。

class Solution(object):
        def findPeakElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            left = 0
            right = len(nums)-1
            while left <= right:
                print left, right
                if left == right:
                    return left
                mid = left + (right -left) / 2 
                # 如果中间小于右边，那么一定在右边
                if nums[mid] < nums[mid+1]:
                    left = mid + 1
                # 左边不小于右边，那么直接把右边弄到中间
                else:
                    # right不可以是mid-1，万一正好是mid，就跳过了，因为并没有比对mid的值
                    right = mid

## 总结 ##

[https_leetcode-cn.com_problems_find-peak-element_description]: https://leetcode-cn.com/problems/find-peak-element/description/