162. Find Peak Element.md

162. Find Peak Element

https://leetcode.com/problems/find-peak-element/description/

solution

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        
        l = 0
        r = len(nums) - 1

        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < nums[mid + 1]:
                l = mid + 1
            else:
                r = mid  # 大于等于证明前面有peak
        return l  # 注意是l

• 一次遍历

def findPeak(arr) :
    n = len(arr)
 
    # first or last element is peak element
    if (n == 1) :
      return 0
    if (arr[0] >= arr[1]) :
        return 0
    if (arr[n - 1] >= arr[n - 2]) :
        return n - 1
  
    # check for every other element
    for i in range(1, n - 1) :
  
        # check if the neighbors are smaller
        if (arr[i] >= arr[i - 1] and arr[i] >= arr[i + 1]) :
            return i

class Solution(object):
    def findPeakElement(self, nums):   
        for i in range(1, len(nums)):
            if nums[i - 1] > nums[i]:
                return i - 1
        return len(nums) - 1

• 二分搜索
  • 找到中间mid元素后，和后面的元素比较大小，如果大于，则说明峰值在前面，如果小于则在后面

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1

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

时间复杂度：O(log(n))
空间复杂度：O(1)

follow up

1901. Find a Peak Element II

Ceiling in a sorted array