LeetCode 162. 寻找峰值
题目描述
题意分析
寻找数组中任意一个严格大于左右相邻元素的位置，返回它的下标。可能存在多个峰值，不要求返回最高峰、最左峰，也不要求整个数组只有一个峰。
题目保证数组非空且相邻元素不相等，把数组两端之外的值视为负无穷。因此端点只要比唯一的真实邻居大，也可以是峰值；数组只有一个元素时，它就是峰值。要求时间复杂度为 $O(\log n)$，所以不能逐个扫描所有位置。
解法：二分查找上升方向
核心思路
[!blue]
虽然数组整体无序，但本题只需找到任意一个峰，可以在每轮保留一个保证仍有峰值的半区间。比较中点
mid与右邻居mid + 1：若向右上升，就保留[mid + 1, right]；若向右下降，就保留[left, mid]。保证这种收缩正确的关键，是让区间边界始终朝内部更高：
nums[left] > nums[left - 1]，且nums[right] > nums[right + 1]。初始区间覆盖整个数组，两端之外视为负无穷，所以成立；这些表达式只用于说明性质，代码不会访问越界位置。若
nums[mid] < nums[mid + 1]，把左边界改为mid + 1，新左端恰好大于它外侧的mid，右边界性质不变。若nums[mid] > nums[mid + 1]，把右边界改为mid，新右端恰好大于它外侧的右邻居，左边界性质不变。相邻元素不相等，所以这两种情况覆盖全部可能。在这样一个区间中，取其中最大的元素，它与区间内相邻元素不会相等；若它位于端点，又由边界性质保证大于区间外的邻居。因此区间里始终存在原数组的峰值。无需判断“峰值下标”是否单调，也无需证明被丢弃的一半没有峰，只需保住至少一个答案。
上坡时
mid的右邻居更大，mid本身不可能是峰，可以排除；下坡时mid仍可能是峰，必须保留它。循环使用left < right，向下取整的中点满足mid < right，读取mid + 1安全，两个分支也都会缩小区间。最终只剩一个位置，两侧边界性质就保证它是峰值。
解题步骤
- 初始化闭区间
left = 0、right = n - 1。- 当
left < right时，计算mid = left + (right - left) / 2。- 若
nums[mid] < nums[mid + 1]，令left = mid + 1，保留上升方向的右半区间。- 否则令
right = mid，保留包含中点的左半区间。- 区间缩为单点时返回
left，即所找到峰值的下标。
代码实现
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 朝更高的一侧收缩，峰值一定存在于该侧。
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
func findPeakElement(nums []int) int {
left := 0
right := len(nums) - 1
for left < right {
mid := left + (right-left)/2
// mid 和 mid+1 的坡度决定峰值所在方向。
if nums[mid] < nums[mid+1] {
left = mid + 1
} else {
right = mid
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮把候选区间缩小到至多原长度的一半向上取整，单轮只比较两个元素。
- 空间复杂度：$O(1)$，只保存左右边界和中点。
关键点总结
[!green]
- 二分保留的是“至少存在一个峰值”的区间，数组本身不需要有序。
- 两端相对区间外邻居更高的性质，在每次更新后继续成立，最终保证单点是峰。
- 上坡可以排除中点，下坡必须保留中点；
left < right同时保证右邻居访问安全。
易错点总结
[!yellow]
- 将循环写成
left <= right，会在只剩一个位置时仍访问mid + 1，可能越界。- 上坡时只令
left = mid，在两个元素的区间中可能无法前进，造成死循环。- 下坡时令
right = mid - 1，会丢掉可能就是答案的中点，也破坏右边界性质。- 不要把数组外侧真的补成某个合法整数极值；负无穷是题目的概念边界，无需存储。
- 返回值应是
left这个下标，而非nums[left]这个数值；本方法也不保证找到某个指定峰。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 852. 山脉数组的峰顶索引 | 中等 | 原题保证整个数组是单峰山脉，本题可能多个峰，只需沿上升方向找到其中一个。 |
| 1901. 寻找峰值 II | 中等 | 把一维峰值扩展到矩阵，需要先选某列最大值，再根据相邻列方向缩小范围。 |
| 1095. 山脉数组中查找目标值 | 困难 | 通过中点与相邻值的坡向保留必含峰值的一侧；本题寻找任意局部峰值，该题先定位山顶再分别搜索两侧。 |
| 补充题 110. 寻找数组的局部最小值 | 中等 | 都根据中点与相邻值的趋势二分；本题朝上升侧寻找峰，补充题朝下降侧找谷。 |