LeetCode 852. 山脉数组的峰顶索引
目录
题目描述
题意分析
给一个「山脉数组」，即存在唯一一个位置
i（0 < i < n - 1），使得数组在[0, i]上严格递增、在[i, n - 1]上严格递减，要求返回这个i。返回的是下标而不是峰顶的值，这是本题第一个容易看错的地方。题目条件给得非常慷慨，每一条都在指路。严格递增递减意味着数组里不存在相邻相等的元素，因此比较任意一对相邻元素时，结果非大即小，不会出现模棱两可的平台。唯一峰顶意味着不必考虑多个候选。峰顶不在两端意味着
arr[0] < arr[1]与arr[n-2] > arr[n-1]天然成立，端点永远不是答案。最强的信号在进阶要求里：数组长度可以到 $10^5$，而题目明确要求在 $O(\log n)$ 时间内完成。从头扫一遍找最大值当然能过测试数据，但它直接违背了题目想考的东西——面试场景下这等于没做。
数组整体当然是无序的，不能直接查找。但换个角度看：把每个位置
i映射成一个布尔值「arr[i] < arr[i+1]是否成立」，得到的这串布尔值一定长成true, true, ..., true, false, ..., false的形状。峰顶恰好就是第一个false出现的位置。一个从true单调翻转到false的序列，天然允许每次砍掉一半的搜索范围。边界方面，题目保证
n >= 3，所以至少有一个合法峰顶；而只要把搜索区间的右端限制在n - 1，访问arr[mid + 1]就永远不会越界。
解法：二分查找上升坡结束位置
核心思路
山脉数组先严格上升、再严格下降。比较
arr[mid]与arr[mid + 1]：
- 若
arr[mid] < arr[mid + 1]，mid位于上升坡，峰顶一定在右侧；- 否则
mid位于峰顶或下降坡，峰顶一定在mid或左侧。二分始终维护“峰顶位于闭区间
[left, right]”这一不变量。上升时mid不可能是答案，令left = mid + 1；下降时mid仍可能是答案，令right = mid。循环条件
left < right保证向下取整的mid小于right，所以访问arr[mid + 1]安全。区间收敛为单点时，该下标就是唯一峰顶。
解题步骤
- 初始化搜索区间为
[0, n - 1]。- 当
left < right时，计算向下取整的中点。- 若中点右侧仍在上升，排除
mid及其左侧。- 否则保留
mid，将右边界收缩到它。- 返回最终的
left。例如
[3,4,5,1]：第一次mid = 1，4 < 5，区间变为[2,3]；第二次mid = 2，5 > 1，区间变为[2,2]，返回峰顶下标 2。
代码实现
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)$。
关键点总结
- 二分不要求原数组整体有序，只要求判断结果能确定答案所在方向。
left = mid + 1与right = mid的差异取决于mid能否被排除。left < right、向下取整中点和right = mid必须配套使用。- 返回的是峰顶下标，不是峰顶元素值。
易错点总结
- 上升分支写成
left = mid，在两元素区间会死循环。- 下降分支写成
right = mid - 1，可能直接丢掉峰顶。- 使用
left <= right却保留right = mid，单点区间无法收缩。- 返回
arr[left]会得到峰顶值，而题目要求下标。- 与
arr[mid - 1]比较需要额外处理mid = 0，更容易越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 162. 寻找峰值 | 中等 | 不保证先升后降，可能有多个峰，靠「两端视作负无穷」保证二分必然收敛 |
| 1095. 山脉数组中查找目标值 | 困难 | 先用本题找峰，再在升降两段各做一次二分，且访问次数受接口限制 |
| 941. 有效的山脉数组 | 简单 | 反过来判定形状是否合法，必须线性走完并检查峰不在两端 |
| 845. 数组中的最长山脉 | 中等 | 允许多个山脉且有平台，改用左右两侧的上升长度递推 |
| 33. 搜索旋转排序数组 | 中等 | 判据换成「哪半边有序」，需要与目标值联合判断走哪边 |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 同样是找拐点，但拿 arr[mid] 与右端点比较而非与邻居比较 |
| 278. 第一个错误的版本 | 简单 | 最纯粹的「找第一个 true」，判据由接口给出，可直接套同一份模板 |
| 35. 搜索插入位置 | 简单 | 找下界，右端要取 n 才能容纳「插到末尾」这个答案 |
| LCR 069. 山脉数组的峰顶索引 | 简单 | 与本题同题，可直接套用 |