162. 寻找峰值
Difficulty: 中等
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 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。
提示：
1 <= nums.length <= 1000-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
进阶：你可以实现时间复杂度为 O(logN)的解决方案吗？
Solution
解法一：遍历数组，找到符合其值大于左右相邻值元素的索引，注意数组的第一个和最后一个元素的边界条件，比如[3,2,1]这种情况3可以被认为是峰值。
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
for i in range(len(nums)):
if i == 0 and nums[i] > nums[i+1]:
return 0
if i > 0 and i < len(nums)-1 and nums[i] > nums[i-1] and nums[i] > nums[i+1]:
return i
if i == len(nums)-1 and nums[-1] > nums[len(nums)-2]:
return len(nums)-1
解法二：二分查找。一开始我是没有想到二分查找能和这道题建立联系，因为一般只有在数据有序的前提下才使用二分查找。
nums[mid]和nums[mid+1]比较：
如果nums[mid]小于nums[mid+1]，那么mid的右侧只有两种情况，一种是一直往上升，另外一种是上下波动，但是不管怎么样mid的右侧一定存在一个峰值，nums[mid]大于等于nums[mid+1]的情形同理。
直到left和right相遇，返回left或者right即可。
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums)-1
while left < right:
m = (left + right) // 2
if nums[m] < nums[m+1]:
left = m + 1
else:
right = m
return right