LeetCode50天刷题计划第二季（Day 29 — 寻找峰值（11.10-12.10）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

芜湖 今日就是我打翻身仗的时候！
社会会教会人很多东西，我相信所有吃的亏都是我走过的路
总有一天凭借我的学习能力我会成为一个出色的人的！（各方面）

一、题目

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log 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。

提示

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

二、思路

首先，爆破的方法是O(n)，即遍历每个元素，题目要求时间复杂度O(logn)，所以需要二分查找。
对于任意一个位置的值，因为相邻元素一定不相等，而我们的目的是找到一个峰值，因此只要不断往高的地方走，就能到达峰值。对于任意位置，左右元素只会出现四种情况：左<中<右(往右走)；左>中>右（往左走）；左<中>右（找到峰值）;左>中<右（往右走）。
即：若左<中>右（找到峰值），若中<右，舍弃左半边，否则往左走。
这个思路的正确性基于以下分析：对于一个序列，考虑其边界元素（以左边元素i为例，已知i-1为无穷小，若i+1i,则将i+1看做首个元素，继续向后试探，由此，若遍历到末尾还没get，由于最后一个元素是无穷小，仍能找到。）
总结一下，对于一个满足 nums[x] > nums[x - 1] 的位置，x 的右边一定存在峰值；或对于一个满足 nums[x] > nums[x + 1] 的位置，x 的左边一定存在峰值。

三、代码

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:    
        left=0
        right=len(nums)-1
        while(1): #循环
            if(left==right): #只剩一个元素
                return 0
            if(left+1 == right): #只剩两个元素
                if(nums[left]>nums[right]):
                    return left
                else:
                    return right
            mid=(left+right+1)//2
            if(nums[mid-1]<nums[mid] and nums[mid]>nums[mid+1]): #移动
                return mid
            elif(nums[mid-1]<nums[mid]):
                left=mid
            else:
                right=mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20