題目描述
峰值元素是指其值大于左右相鄰值的元素。
給定一個輸入數(shù)組 nums缝驳，其中 nums[i] ≠ nums[i+1]慈俯，找到峰值元素并返回其索引。
數(shù)組可能包含多個峰值起愈，在這種情況下只恨，返回任何一個峰值所在位置即可。
你可以假設(shè) nums[-1] = nums[n] = -∞抬虽。
示例
示例 1：
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素官觅，你的函數(shù)應(yīng)該返回其索引 2。
示例2
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數(shù)可以返回索引 1阐污，其峰值元素為 2休涤；
或者返回索引 5， 其峰值元素為 6笛辟。
說明
你的解法應(yīng)該是 O(logN) 時間復(fù)雜度的功氨。
解答方法
方法一：二分法
思路
nums[i] !=nums[i+1]
nums[?1]=nums[n]=?∞
若找到一個值，右側(cè)的下個值更大手幢，則在右側(cè)一定存在峰值捷凄，反之，自身或者左側(cè)一定存在峰值围来。
看到O(log(n))跺涤，想到二分法。
代碼
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) -1
while left<right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
時間復(fù)雜度
O(logn)
空間復(fù)雜度
O(1)
