LeetCode 162. 寻找峰值
目录
题目描述
题意分析
在一个整数数组里找峰值——严格大于左右两个相邻元素的位置——并返回它的下标。数组本身完全无序，峰值可能有很多个，题目明确说返回任意一个即可，不要求最左、最高或全部；这一点直接决定了判题方式（判「是不是峰」而不是「等不等于某个下标」），也放宽了解法的自由度。
两条约束是整道题的地基。第一条：任何相邻两个元素都不相等，所以在任意相邻位置之间，坡度只有「上」或「下」两种，不存在需要额外处理的平台。第二条：数组两端外侧视为负无穷（
nums[-1] = nums[n] = -∞），所以哪怕整个数组单调递增，最后一个元素也因右邻是-∞而成为峰——峰值必然存在。这两条合在一起，正是后面能用二分的前提：坡度判据无歧义，且「答案存在」的保证不会在收缩区间时丢失。题目还给了一个强信号：要求 $O(\log n)$ 时间。对一个无序数组提对数级要求，等于明说线性扫描不是期望答案，必须找到某种能每轮砍半的结构。
边界情形：
n = 1时唯一元素两侧都是-∞，答案就是0；n = 2时较大的那个是峰；单调数组的峰在端点上。取值可到int边界，正负都有，不能依赖数值本身的任何特征。
解法：二分查找上升方向
核心思路
问题关键：数组虽然无序，但相邻元素的坡度能确定哪一侧必然存在峰值。若
nums[mid] < nums[mid + 1]，沿上坡向右走，最终要么遇到下降，要么到达右端点，两种情况都会得到峰值；下坡时向左同理。为什么选该解法：线性扫描是 $O(n)$，而题目要求 $O(\log n)$。坡度提供了每轮排除一半区间的依据，所以可以二分；这里依赖的不是数组有序，而是「某一半必有答案」。
不变量：闭区间
[left, right]内始终至少有一个峰值。上坡时令left = mid + 1；下坡时令right = mid，因为mid仍可能是峰，不能丢弃。区间缩到单点时，该位置就是答案。
解题步骤
- 初始化闭区间
[left, right] = [0, n - 1]。- 当
left < right时取中点；此时mid < right，访问mid + 1不会越界。- 若
nums[mid] < nums[mid + 1]，令left = mid + 1；否则令right = mid。- 区间收缩到一个位置后返回
left。例如
[1,2,1,3,5,6,4]的区间依次为[0,6] → [4,6] → [4,5] → [5,5]，返回峰值下标 5。
代码实现
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)$。
关键点总结
- 二分依赖的是可排除一半的判据，不要求原数组整体有序。
- 核心不变量是
[left, right]内必有峰，而不是峰值下标满足单调性。- 上坡分支排除
mid，下坡分支保留mid，因此边界更新不对称。- 相邻元素不等和两端视为负无穷，共同保证峰值存在且坡度方向明确。
易错点总结
- 循环写成
left <= right：[1]会访问越界的nums[mid + 1]。- 上坡时写
left = mid：[1,2]的区间无法缩小，会死循环。- 下坡时写
right = mid - 1：[2,3,1]会丢掉真正的峰值mid = 1。- 返回
nums[left]：题目要求的是下标，不是峰值本身。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 852. 山脉数组的峰顶索引 | 中等 | 保证先升后降的单峰数组，同一坡度判据但峰唯一，是本题去掉多峰干扰的受限版 |
| LCR 069. 山脉数组的峰顶索引 | 简单 | 与 852 同题换皮，适合检验坡度二分的模板能否脱稿写对 |
| 1095. 山脉数组中查找目标值 | 困难 | 先用峰值二分切出两段单调区间，再各做一次常规二分，且受访问次数上限约束 |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 同为无目标值的结构二分，谓词换成与 nums[right] 比较来判断最小值所在半边 |
| 33. 搜索旋转排序数组 | 中等 | 有目标值但整体无序，每轮先判定哪半边有序、再决定目标落点，谓词比本题多一层 |
| 704. 二分查找 | 简单 | 全局有序的标准二分，对照本题理解「有序只是充分条件，排除谓词才是必要条件」 |