题解 | #寻找峰值#

寻找峰值，复杂一点的解法+对官方题解的理解

如果峰值存在于一个区间内，必有左端和右端单调性相反。由于没有想到官方题解 那种间接使用nums[−1]=nums[n]=−∞和间接得到峰值的方法，所以添加了几对数组首尾的边界条件。

对官方题解理解：数组首尾的单调性是已知的，左单增，右单减，所以官方题解直接利用这点，找到中点，如果此处是单减的nums[mid+1]<nums[mid]，则左、中单调性相反，左、中必然存在峰值，保留中点处较大者nums[mid]，因为它有可能就是峰值，此时区间缩小一半，区间首尾单调性同样是已知的，左单增，右单减。再次找到中点，如果此处是单增的nums[mid+1]>nums[mid]，则中、右单调性相反，中、右必然存在峰值，保留中点处较大者nums[mid+1]，因为它有可能就是峰值，此时区间又缩小一半。继续相同操作....。所有的操作都是在把区间往峰值处收缩，最后收缩到区间内只有一个元素就是峰值。

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        # 含有峰值的那一段，左右单调性相反
        left, right = 0, len(nums)-1          # nums[-1] = nums[n] = −∞
        while left <= right:
            mid = (left+right)//2
            if mid-1<0 and mid+1>len(nums)-1: # 处理只有一个元素的情况
                return mid
            elif mid-1<0:                     # mid在左边界，nums[-1]=−∞，只比较右
                if nums[mid]>nums[mid+1]:
                    return mid
            elif mid+1>len(nums)-1:           # mid在右边界，nums[n]=−∞，只比较左
                if nums[mid]>nums[mid-1]:
                    return mid
            else:
                if nums[mid-1] < nums[mid] > nums[mid+1]: # 中间，比较左右
                    return mid
            
            if left == 0:  # 只考虑一边，left在左边界，只用看mid处
                if nums[mid+1] - nums[mid] <0: 
                    right = mid-1
                else:
                    left = mid+1
            else:
                if (nums[mid+1] - nums[mid])*(nums[left] - nums[left-1]) < 0: # 单调性相反
                    right = mid-1
                else:
                    left = mid+1