题解 | #寻找峰值#

import re
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        # write code here
        l = 0
        r = len(nums)-1

        while l <r:
            mid  = l+(r-l)//2
            if nums[mid]<nums[mid+1]:
                l = mid+1
            else: # nums[mid] > nums[mid+1]
                r = mid
        return l

思路关键：通过分析知道，右侧一定有峰值

暴力的思路，直接扫一遍list，这样复杂度是O(n)

利用二分法简化：O(log(n))

注意题中给出的nums[-1]=nums[n]=-∞

假设有一个中间元素满足mid[i-1]<mid[i]<mid[i+1]，要去左边还是右边呢？没法判断

换一个角度：右边在增长，右边一定有一个峰值，左边不用管了

如果右边开始下降，则左边一定有峰值了