LeetCode 162 Find Peak Element

LeetCode

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] = -∞.

You must write an algorithm that runs in O(log n) time.

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.

Constraints:

1 <= nums.length <= 1000 -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
* nums[i] != nums[i + 1] for all valid i.

题目大意：

找数组极大值

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. mid - 1 >= 0

Python代码：

def findPeakElement(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if mid >= 1 and nums[mid - 1] < nums[mid]:
			start = mid
		else:
			end = mid
	return start if nums[start] > nums[end] else end

def findValleyElement(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if mid >= 1 and nums[mid - 1] >= nums[mid]:
			start = mid
		else:
			end = mid
	return start if nums[start] <= nums[end] else end

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)