寻找峰值
🟡 中等题目描述
峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。如果数组存在多个峰值，则返回任何一个峰值所在位置即可。
示例 1
输入：nums = [1, 2, 3, 1]
输出：2
解释：3 是峰值元素，返回索引 2示例 2
输入：nums = [1, 2, 1, 3, 5, 6, 4]
输出：1 或 5
解释：返回索引 1（峰值 2）或索引 5（峰值 6）都可以提示
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
解法
参考答案 (2 个标签)
二分查找 O(log n)
思路
如果 nums[mid] < nums[mid + 1]，说明右侧一定有峰值（爬坡方向）；否则左侧一定有峰值。
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
function findPeakElement(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}复杂度分析
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
为什么一定有峰值？
- 数组边界可以视为负无穷
- 如果一直上升，最后一个元素是峰值
- 如果一直下降，第一个元素是峰值
- 如果有升有降，转折点就是峰值