0162._find_peak_element.md

162. Find Peak Element

难度: Medium

刷题内容

原题连接

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

内容描述

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.
Note:

Your solution should be in logarithmic complexity.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

最直观的是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 

思路 2 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

O(lgN) 解法

这是一个经典题目, 首先题目说了You may imagine that nums[-1] = nums[n] = -∞，并且num[i] ≠ num[i+1]， 所以一定是有解的

• a[mid] >= a[mid+1] only look at the left side
• a[mid] < a[mid+1] 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