<div>
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:
<pre>Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.</pre>
Example 2:
<pre>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.</pre>
Constraints:
1 <= nums.length <= 1000-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1nums[i] != nums[i + 1]for all validi.
</div>
题目大意：
找数组极大值
解题思路：
N/A
解题步骤：
N/A
注意事项：
- mid - 1 >= 0
Python代码：
1
2
3
4
5
6
7
8
9def 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
1
2
3
4
5
6
7
8
9def 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)
