Leetcode** 162. Find Peak Element

Description: A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

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

Link: 162. Find Peak Element

Examples:

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: 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.

思路: 顺序检索，从0，到最后一个元素，从第一个元素开始想，如果下一个小，则这个值就是局部峰值，返回，否则下一个有可能是，continue.

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.append(float('-inf'))
        for i in range(n):
            if nums[i] > nums[i+1]:
                return i
            else:
                continue

但是上面的复杂度是O(n)，题目要求logn.怎么二分查找呢？二分查找的核心思想就是不断缩小带查找元素所在的区间，区间缩到最小返回。因为按题目意思，必然存在一个局部峰值，数组头和尾的两边设想存在最小负数，所以对于头，只要下一个元素小于它，它就是局部峰值，只要尾的前一个元素小于它，它就是局部峰值。当我们到了mid, 如果mid+1大于它，那么向右呈现上升趋势，峰值必然在mid右侧，l=mid+1，反之，呈现下降趋势，峰值必然在mid或者mid的左边,所以r=mid。以left < right结束，最后区间left=right，缩小到一个值，一个index,返回即可。

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

日期: 2021-04-12 是阴天啊