LeetCode LCR 069. 山脉数组的峰顶索引
题目描述
题意分析
数组先严格递增，再严格递减，要求返回唯一峰顶的下标。题目保证输入是合法山脉，峰顶两侧都至少有一个元素，所以峰顶一定在下标 $1$ 到
n - 2之间。进阶要求对数时间。虽然整个数组不是单调排列，但任意位置与右邻的升降关系可以判断它处在峰顶哪一侧，这为二分提供了方向。
解法：按坡度二分峰顶
核心思路
[!blue]
设峰顶下标为
p。对可以访问右邻的下标i，若i < p，则arr[i] < arr[i + 1]，处于上坡；若i >= p，则arr[i] > arr[i + 1]，已经开始下坡。因此判定arr[i] > arr[i + 1]先为假、后为真，第一个为真的位置就是峰顶。将候选闭区间初始化为
[1, n - 2]，始终保证峰顶包含在其中。比较中点与右邻后：
arr[mid] > arr[mid + 1]：中点位于峰顶或下降段，峰顶在mid或左侧，令right = mid。不能排除mid，因为它可能恰好就是峰顶。arr[mid] < arr[mid + 1]：中点仍在上升段，峰顶严格位于右侧，令left = mid + 1。严格山脉不存在相邻相等的情况，两种分支已经覆盖全部可能。每轮都会缩短区间，又不会移除峰顶；收敛到
left == right时，剩下的唯一候选就是答案。初始右边界不超过
n - 2，以后只会向左移动，所以比较中的mid + 1不会越界。长度为 $3$ 时，初始区间就是[1, 1]，不进入循环也能直接返回唯一可能的峰顶。峰顶靠近任意一端时，也仍在这个候选范围内。
解题步骤
- 初始化
left = 1、right = arr.length - 2。- 在
left < right时取中点，比较arr[mid]与arr[mid + 1]。- 向右下降时令
right = mid，保留中点；向右上升时令left = mid + 1，排除中点。- 区间收敛后返回
left，得到峰顶下标。
代码实现
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 1;
int right = arr.length - 2;
while (left < right) {
int mid = (left + right) >> 1;
if (arr[mid] > arr[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
func peakIndexInMountainArray(arr []int) int {
left, right := 1, len(arr)-2
for left < right {
mid := (left + right) >> 1
if arr[mid] > arr[mid+1] {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮排除约一半候选位置。
- 空间复杂度：$O(1)$，仅保存边界和中点。
关键点总结
[!green]
- 二分利用的是坡度判定的单调性，而不是整个数组数值单调。
- 下降时中点仍可能是峰顶，上升时中点一定不是峰顶，因此两边的收缩方式不同。
[1, n - 2]同时来自峰顶不在端点的保证和访问右邻的需要。- 正确性依赖题目保证的严格单峰结构，不需要为平台或多峰加入额外分支。
易错点总结
[!yellow]
- 仅比较中点与某个固定端点的数值，不能按本题的坡度规则判断峰顶方向。
- 下降时将右边界设为
mid - 1，会丢掉峰顶恰好在中点的情况。- 上升时令
left = mid，可能使区间不再缩小。- 应返回下标，不能返回
arr[left]；题目的目标是峰顶位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 162. 寻找峰值 | 中等 | 同样沿局部上升方向二分，原题可能多个峰，本题保证单一山脉峰顶。 |
| 1095. 山脉数组中查找目标值 | 困难 | 寻找山脉峰顶是子步骤，再分别在升序段和降序段二分目标值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！