LeetCode 852. 山脉数组的峰顶索引
题目描述
题意分析
数组已经保证是山脉形状：先严格递增到某个位置，再严格递减。峰顶唯一，且不在两端，要求返回这个峰顶的下标，而不是峰顶的数值。
不需要验证输入是否为山脉，也不用逐个找最大值。峰顶之前的相邻关系一直是上升，峰顶之后一直是下降，可以根据中点所在的坡向判断峰顶在哪一侧，在对数时间内缩小范围。
解法：二分查找上升坡结束位置
核心思路
[!blue]
用闭区间
[left, right]保存峰顶可能的位置，初始覆盖整个数组。每轮只比较arr[mid]与右邻arr[mid + 1]，判断当前位置是否仍在上坡。如果
arr[mid] < arr[mid + 1]，说明从中点向右还在严格上升，峰顶一定尚未到达。由于山脉只有一个峰，中点及其左侧都不可能是峰顶，令left = mid + 1。否则相邻值处于下降关系，中点已经到达峰顶或位于峰顶右侧，峰顶只可能在中点及其左边。因此令
right = mid，必须保留中点，因为下降的第一对元素恰好从峰顶出发。两个分支都保留唯一峰顶，同时缩小候选区间。循环条件
left < right配合向下取整中点，保证mid < right，因此mid + 1不会超过当前右边界，访问右邻始终安全。当两端相遇时，只剩一个候选位置，直接返回它。二分利用的是坡向从上升变为下降的单调性，不要求整个数组从小到大排列。
解题步骤
- 初始化
left = 0、right = n - 1。- 当
left < right时，计算向下取整的中点mid。- 若中点到右邻仍上升，令
left = mid + 1。- 否则令
right = mid，保留可能就是峰顶的中点。- 区间收敛后返回
left。
代码实现
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
// 左端小于右端且中点向下取整，右邻始终在数组内
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
// 下降时中点仍可能就是峰顶，必须保留
right = mid;
}
}
return left;
}
}
func peakIndexInMountainArray(arr []int) int {
left, right := 0, len(arr)-1
for left < right {
// 左端小于右端且中点向下取整，右邻始终在数组内
mid := left + (right-left)/2
if arr[mid] < arr[mid+1] {
left = mid + 1
} else {
// 下降时中点仍可能就是峰顶，必须保留
right = mid
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log n)$，候选区间每轮折半。
- 空间复杂度：$O(1)$，仅二分下标。
关键点总结
[!green]
- 使用坡度决定方向，不要求全数组升序。
- 中点安全性来自循环条件与取整方式共同约束。
易错点总结
[!yellow]
- 上升时令左端等于中点，两候选时可能停滞。
- 下降时丢掉中点，可能丢掉峰顶。
- 返回峰顶值而非下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 162. 寻找峰值 | 中等 | 同样沿局部上升方向二分，原题可能多个峰，本题保证单一山脉峰顶。 |
| 1095. 山脉数组中查找目标值 | 困难 | 寻找山脉峰顶是子步骤，再分别在升序段和降序段二分目标值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！