162. Find Peak Element

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

solution

• 暴力解: 一次遍历

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元素后，和后面的元素(mid + 1)比较大小，如果大于，则说明峰值在前面，如果小于则在后面

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

follow up

1901. Find a Peak Element II

Ceiling in a sorted array