Skip to content

162 find peak element

162. Find Peak Element

题目: https://leetcode.com/problems/find-peak-element/

难度: Medium

思路:

最直观的是O(N)解法

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i] < nums[i-1]:
                return i-1
        return len(nums) - 1 

O(lgN) 解法

这是一个经典题目

  • a[mid] < a[mid] only look at the left side
  • a[mid] < a[mid] only look at the right side
  • else peak found

证明就是用反证法,或者看peak,因为这里已经限制了num[i] ≠ num[i+1],所以peak element 一定存在。然后a[mid] < a[mid-1],那么说明这里一定是下降的,说明之前一定有一个peak存在,否则我们可以用反证法证明.

写到这里,我非常相信就是binary search能写对其实不容易。

AC代码

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l, r = 0, len(nums) - 1
        while l <= r:
            if l == r : return l
            mid = l + ((r - l) >> 2)
            if nums[mid] < nums[mid+1]:
                l = mid + 1
            else:
                r = mid


回到顶部