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+1
总结一下，对于一个满足 nums[x] > nums[x - 1] 的位置，x 的右边一定存在峰值；或对于一个满足 nums[x] > nums[x + 1] 的位置，x 的左边一定存在峰值。
三、代码
class Solution:def findPeakElement(self, nums: List[int]) -> int: left=0right=len(nums)-1while(1): #循环if(left==right): #只剩一个元素return 0if(left+1 == right): #只剩两个元素if(nums[left]>nums[right]):return leftelse:return rightmid=(left+right+1)//2if(nums[mid-1]nums[mid+1]): #移动return midelif(nums[mid-1]