LeetCode 1095. 山脉数组中查找目标值
目录
题目描述
题意分析
给定一个山脉数组：存在某个下标
peak，使得下标 0 到peak严格递增、peak到末尾严格递减，两段都严格单调所以不会出现平台。要在里面找target，并返回最小的下标；找不到返回 -1。因为左右两段可能都含有同一个值，「最小下标」这个要求是有实际约束力的，不能随便返回一个命中位置。这题最特殊的地方是：数组本身拿不到，只能通过
MountainArray接口访问，get(i)取单个元素、length()取长度，而且题目明确限制get的调用次数不能超过 100 次，超了直接判错。这条限制才是真正的出题意图——它把「遍历一遍就完事」的解法彻底封死，要求每一次读取都得物有所值。配合看规模：数组长度最多 $10^4$，$\log_2 10^4 \approx 13.3$，也就是说一次二分大约 14 步。100 次的预算刚好够做三轮二分再富余一些，这个数字几乎是在提示解法的形状。
边界要留意：长度最小为 3，所以左右两段都非空；峰顶自身属于递增段的末尾，查找时不能把它漏掉；
target有可能只出现在降序段里。
解法：找峰顶 + 两次有序二分
核心思路
get最多调用 100 次，不能线性读取数组。山脉数组虽然整体无序，但以峰顶为界，可拆成一个严格升序段和一个严格降序段，因此用三次二分完成：先找峰顶，再依次搜索左右两段。找峰时比较
get(mid)与get(mid + 1)：前者较小表示仍在上坡，峰顶必在右侧；否则峰顶在mid或其左侧。搜索目标时，升序段中值偏小向右，降序段中值偏大向右。区间不变量：找峰阶段峰顶始终位于闭区间
[left, right]；查找阶段若目标存在于当前单调段，它始终位于[left, right]。先查[0, peak]，命中立即返回，便能保证答案是最小下标。
解题步骤
- 只调用一次
length()，记录数组长度。- 在
[0, n - 1]上二分找峰。循环使用left < right，保证mid + 1不越界。- 在
[0, peak]上按升序二分；这里包含峰顶。- 左段命中就返回，因为其任何下标都小于右段下标。
- 否则在
[peak + 1, n - 1]上按降序二分，仍未命中则返回 -1。对
arr = [1,2,3,4,5,3,1]、target = 3，先得到峰顶下标 4；升序段直接命中下标 2，因此无需再查右侧下标 5，答案自然是更小的 2。
代码实现
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int n = mountainArr.length();
int left = 0;
int right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int value = mountainArr.get(mid);
int nextValue = mountainArr.get(mid + 1);
if (value < nextValue) {
left = mid + 1;
} else {
right = mid;
}
}
int peak = left;
int ans = binarySearch(mountainArr, 0, peak, target, true);
if (ans != -1) {
return ans;
}
return binarySearch(mountainArr, peak + 1, n - 1, target, false);
}
private int binarySearch(MountainArray mountainArr, int left, int right, int target, boolean asc) {
while (left <= right) {
int mid = left + (right - left) / 2;
int value = mountainArr.get(mid);
if (value == target) {
return mid;
}
// 升序和降序区间的移动方向相反。
if ((asc && value < target) || (!asc && value > target)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
func findInMountainArray(target int, mountainArr *MountainArray) int {
n := mountainArr.length()
left := 0
right := n - 1
for left < right {
mid := left + (right-left)/2
value := mountainArr.get(mid)
nextValue := mountainArr.get(mid + 1)
if value < nextValue {
left = mid + 1
} else {
right = mid
}
}
peak := left
ans := searchMountain(mountainArr, 0, peak, target, true)
if ans != -1 {
return ans
}
return searchMountain(mountainArr, peak+1, n-1, target, false)
}
func searchMountain(arr *MountainArray, left int, right int, target int, asc bool) int {
for left <= right {
mid := left + (right-left)/2
value := arr.get(mid)
if value == target {
return mid
}
// asc 标识当前区间是升序还是降序。
if (asc && value < target) || (!asc && value > target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(\log n)$。找峰每轮调用两次
get，两次目标搜索每轮各调用一次，总调用量不超过约 $4\lceil\log_2 n\rceil$；当 $n \leq 10^4$ 时约为 56 次。- 空间复杂度：$O(1)$，只使用常数个下标和临时值。
关键点总结
- 调用次数限制决定必须使用对数算法；不能先把接口内容复制成普通数组。
- 用相邻元素判断坡向，先定位唯一峰顶，再获得两个单调区间。
- 左段包含峰顶，右段不含峰顶；先左后右保证最小下标。
- 同一个二分函数用
asc表示顺序，降序区间的移动方向与升序相反。
易错点总结
- 找峰使用
left <= right时，mid可能到达末尾，访问mid + 1越界；应使用left < right。- 左段写成
[0, peak - 1]会漏掉target恰为峰值的情况。- 降序段沿用升序更新方向，会排除真正答案；降序中值偏大时应向右。
- 先搜右段可能返回较大下标；必须先搜左段并在命中后立即返回。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 852. 山脉数组的峰顶索引 | 简单 | 只求峰顶下标的二分 |
| 162. 寻找峰值 | 中等 | 无序数组中找任意峰值 |
| 941. 有效的山脉数组 | 简单 | 山脉形状的合法性判定 |
| 845. 数组中的最长山脉 | 中等 | 求最长山脉子数组 |
| 33. 搜索旋转排序数组 | 中等 | 分段有序数组上的二分 |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 用相邻或端点比较定分界 |