Leetcode 162. 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.

解决思路

因为题目要求对数复杂度，而且是一个查找问题，直觉使用二分查找。与二分查找的不同在于对high重新赋值为mid而不是mid-1，因为我们希望mid在 nums[mid] > nums[mid+1] 的同时再比较一次 nums[mid-1] 和 nums[mid]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findPeakElement(self, nums: 'List[int]') -> 'int':
        if not nums:
            return -1
        n = len(nums)
        low, high = 0, n-1
        while low < high:
            mid = (low+high)//2
            if nums[mid] < nums[mid+1]:
                low = mid + 1
            else:
                high = mid
        return low