山脉数组二分查找全解：三次二分破解 LeetCode 1095-北京尧图网络

前几天刷题群里有朋友卡在 LeetCode 1095 上说山脉数组的解法绕来绕去边界条件一多就犯迷糊。这道题其实很有代表性——它是“二分查找变体”里最典型的综合题之一把“峰值查找”和“两侧有序区间的定向二分”串在一起考我当年第一次做也踩了不少坑。这篇笔记就把我反复打磨后的完整解法和思考过程写出来从题意拆解、三次二分的逻辑链条到边界处理和调试技巧一次讲透。不管你是刚开始刷二分的入门选手还是想体系化梳理变体的老手这篇都有值得参考的地方。1. 从题目到思路为什么“山脉数组”不能用普通二分一把梭1.1 先搞清楚题面到底在说什么LeetCode 1095 的完整描述是这样的给你一个“山脉数组”mountainArr它满足先严格递增后严格递减的性质也就是说存在一个下标peak使得mountainArr[0] mountainArr[1] ... mountainArr[peak]然后从peak之后开始严格递减直到数组末尾。你要在这个数组里找到目标值target的最小下标如果不存在就返回 -1。举个例子数组[1, 2, 3, 4, 5, 3, 1]5 就是峰顶下标是 4。如果target 3那么数组里有两个 3分别在下标 2 和下标 5题目要求返回最小的那个也就是 2。这类数组的“字形”画出来就像一座山左边上坡、右边下坡因此得名“山脉数组”。它和普通的“有序数组”最大的区别在于整个数组不是全局单调的而是“分段单调”——左半段升序右半段降序。很多人拿到这题的第一反应是那就直接遍历一遍呗从头扫到尾找 target遇到就返回。这当然能过但题目里明确了平台对时间复杂度的限制最多调用 100 次get方法。也就是说你必须用 O(log n) 的方案线性扫描在数据量大的时候大概率超时。这道题的核心考点就是在非全局有序的数据结构中仍然使用二分查找这正好是二分思想最需要灵活变通的地方。1.2 为什么不能直接对整个数组做普通二分普通二分查找的前提是“数组整体有序”你取中点mid比较nums[mid]和target然后可以放心地丢掉一半区间因为目标值不可能出现在被丢掉的那一半里。但山脉数组不行。你在中点拿到一个值mountainArr[mid]如果它小于 target你能确定 target 在左边还是右边吗不能。它可能在左边上坡段也可能在右边下坡段。如果mountainArr[mid]大于 target同样没法直接判断该往哪边走。因为数组本身存在“两个方向”普通二分的“一侧丢弃”策略直接失效。所以题的破局点在于既然整个数组不是单调的那就把它拆成两个单调区间来处理。拆的关键是先找到峰顶位置peak——在峰顶左边数组严格递增在峰顶右边数组严格递减。这样一来问题从“在一个形态复杂的数组里搜索”变成了“在两个各自有序的区间里分别搜索”。两次搜索都满足普通二分的前提问题就简单了。这里有个隐含的重点值得多说一句峰顶左边和右边的区间排序方向不同。左边是升序可以直接用标准的nums[mid] target判断右边是降序比较逻辑要反过来。很多人正是因为忽略了“降序二分”和“升序二分”的比较方向差异导致 AC 不了。后面第 2 章我会专门拆这个细节。1.3 整体解法三次二分各司其职想清楚上面这些方案就非常清晰了。总体上需要三次二分分工如下第一次二分找到峰顶下标peak。第二次二分在左区间[0, peak]严格递增里找 target找到了直接返回因为题目要求最小下标而左边的下标一定更小。第三次二分如果左区间没找到再到右区间[peak1, n-1]严格递减里找 target找到返回下标找不到返回 -1。三次二分各司其职每次都是 O(log n)总时间复杂度 O(log n)完全符合平台“最多调用 100 次 get”的限制。这个思路本身不难理解真正容易出问题的是第一和第二、第三次二分各自的边界条件。下面我把每一步掰开揉碎来讲。2. 第一座山峰值查找的二分细节2.1 比较对象的选择和邻居比而不是和 target 比普通二分查找的目标值是一个具体的数比如 target。但找峰值时我们的“目标”不是一个数值而是一个位置——数组中那个“比左边大、比右边也大”的点。因此找峰值的二分里比较的对象不是 target而是相邻元素。具体做法是取中点mid比较mountainArr[mid]和mountainArr[mid 1]。如果mountainArr[mid] mountainArr[mid 1]说明当前处于“上坡”阶段峰顶一定在 mid 的右侧所以left mid 1。如果mountainArr[mid] mountainArr[mid 1]说明当前处于“下坡”阶段峰顶是 mid 或者在 mid 的左侧所以right mid。这里的关键是当mountainArr[mid] mountainArr[mid 1]时不能直接把right更新为mid - 1而要保留mid。因为mid本身可能就是峰顶。你把峰顶丢了后面就永远找不到它了。2.2 为什么终止条件要写成left right峰值查找的二分循环条件一般是while (left right)而不是普通二分常用的while (left right)。原因和上面说的“保留 mid”直接相关。当区间收窄到只剩一个元素时——也就是left right——这个位置就是我们要的峰顶。此时如果继续进入循环mid会和left、right相等代码可能陷入死循环或者越界。所以循环条件设为left right循环结束时left right这个位置就是峰顶直接返回即可。这个写法和标准二分查找的“闭区间三要素”有一个明显差别标准写法里left right时还需要再判断一次nums[mid] target但峰值查找不需要因为我们要的是“极值位置”区间收缩到一点时那个点必然满足峰顶的性质前提是数组结构符合山脉定义。注意找峰值时为什么只比较mid和mid 1不需要比较mid和mid - 1因为山脉数组严格递增后严格递减相邻元素不会相等。比较mid和mid 1只需要保证mid 1不越界而mid在left right的前提下mid 1最大是right不会等于n。如果改成比较mid - 1则在left 0时可能访问-1还需要额外的越界判断反而麻烦。2.3 峰值二分的完整实现用 Python 写出来就是这样def find_peak(mountainArr): left, right 0, mountainArr.length() - 1 while left right: mid left (right - left) // 2 if mountainArr.get(mid) mountainArr.get(mid 1): left mid 1 else: right mid return left这里我特意用了left (right - left) // 2而不是(left right) // 2两个写法在数学上等价但前者可以避免left right在极端情况下溢出。虽然 LeetCode 平台一般不会把数组长度设到溢出级别但这是一个好习惯建议所有二分都这么写。这段代码里最反直觉的地方在else分支为什么mountainArr[mid] mountainArr[mid 1]时right mid而不是更“自然地”写成right mid - 1还是那句话mid可能就是峰顶。比如数组[1, 3, 2]第一次循环mid 1arr[1] 3 arr[2] 2如果right变成 0那峰顶 1 就直接被排除在搜索区间之外了后面啥也找不到。保留mid区间从[0, 2]收窄到[0, 1]再下一轮mid 0arr[0] 1 arr[1] 3left 1此时left right 1退出循环返回 1正确。3. 左右开弓两个有序区间的定向二分3.1 左区间标准升序二分的直接套用拿到峰顶peak之后左区间[0, peak]是一个严格递增的数组。搜索 target 就是一个标准的升序二分查找凡是刷过几道二分题的人都很熟悉def search_increasing(mountainArr, target, left, right): while left right: mid left (right - left) // 2 val mountainArr.get(mid) if val target: return mid elif val target: left mid 1 else: right mid - 1 return -1这里用while (left right)是恰当的因为我们要精确找 target区间为空时即left right时停止。找到就返回下标没找到返回 -1。有一个细节值得留意左区间搜索的终止条件和峰值查找不一样这里用的是“闭区间等号”因为搜的是一个具体值不是极值位置。两种二分形态的使用场景不同不能混用。3.2 右区间降序二分的比较方向反转右区间[peak 1, n-1]是严格递减的。很多人在这里写错是因为“惯性思维”把升序二分的写法原封不动搬过来了。但降序区间里数组的趋势反了数值越大下标反而越小。所以比较逻辑要反转def search_decreasing(mountainArr, target, left, right): while left right: mid left (right - left) // 2 val mountainArr.get(mid) if val target: return mid elif val target: right mid - 1 # 注意这里降序时小的值在右边 else: left mid 1 # 大的值在左边 return -1逐行解释一下这个反转在降序数组中mid的值如果小于 target说明 target 所在的区域是“值更大的方向”也就是mid的左侧所以要收缩右边界right mid - 1。如果mid的值大于 target说明 target 在“值更小的方向”也就是右边所以要收缩左边界left mid 1。升序和降序两个函数只有两行left/right的更新写反了但这就是二分里最容易阴沟翻船的地方。我自己也曾经在右区间用升序逻辑结果测试用例里目标值在右区间时永远返回 -1排查半天才意识到是方向搞错了。3.3 主流程先左后右天然满足“最小下标”最后把三次二分串起来class Solution: def findInMountainArray(self, target: int, mountainArr: MountainArray) - int: n mountainArr.length() # 第一次二分找峰顶 left, right 0, n - 1 while left right: mid left (right - left) // 2 if mountainArr.get(mid) mountainArr.get(mid 1): left mid 1 else: right mid peak left # 第二次二分左区间升序 idx self._binary_search_increasing(mountainArr, target, 0, peak) if idx ! -1: return idx # 第三次二分右区间降序 return self._binary_search_decreasing(mountainArr, target, peak 1, n - 1)为什么先搜左区间而不是右区间因为题目要的是最小下标。左区间的所有下标都小于右区间的所有下标所以只要左区间找到了它一定比任何右区间的答案都小直接返回即可。如果左区间找不到才去右区间找。这里还有一个边界上的细节右区间的搜索起点是peak 1而不是peak。因为peak已经在左区间搜索范围内左区间已经把peak这个位置检查过了。重复检查没有意义而且从peak 1开始右区间的严格递减性质更纯粹避免边界歧义。4. 调试实录我在这道题上踩过的四个坑4.1 坑一峰值查找的区间收缩把峰顶丢了一开始写峰值二分时我把else分支写成了right mid - 1被平台一个普通用例直接打脸[1, 3, 2]找目标值 3返回-1。原因前面已经分析过mid是峰顶时被排除搜索区间根本没有包含正确答案。这类 bug 很隐蔽因为不是每个用例都会触发只有当峰顶恰好落在mid位置上才会暴露。排查方法也很简单把每次循环的left、right、mid打印出来跟踪区间变化立刻就能看到峰顶被跳过的过程。4.2 坑二右区间用了升序二分的比较逻辑在search_decreasing里我一开始写的是标准升序逻辑val target时left mid 1导致降序区间的目标值永远搜不到。这个坑的教训是二分查找的“骨架”只是模板真正决定对错的是“区间收缩方向和数组单调方向是否匹配”。写降序二分时最好在纸上先画一个简单的递减数组比如[5, 4, 3, 2, 1]手动走一遍target 2的查找过程确认哪边该缩。手动模拟两步比事后调试省时间得多。举例arr [5, 4, 3, 2, 1], target 2 初始 left0, right4, mid2, arr[2]3 2 降序逻辑arr[mid] target, 说明 target 在右侧left mid 1 3 区间 [3,4], mid3, arr[3]2 2返回 3 如果用了升序逻辑arr[mid] target, right mid - 1 1, target 就被丢在区间外了4.3 坑三混淆了“峰值查找”和“值查找”的循环终止条件峰值查找用while left right返回的是left值查找用while left right返回的是找到的下标或者 -1。这两个条件我一开始没分清在峰值查找里用了结果在left right时还会再算一次mid在某些用例里陷入死循环。区分方法非常直接你是不是在找一个“位置性质”如果是比如“峰顶”“第一个坏版本”“旋转数组的最小值”循环条件是left right区间收敛到一点就是答案如果你是在找一个具体的相等值那循环条件是left right因为相等时就要 return区间为空就是没找到。把这个问题想明白了二分的终止条件就不会再混。4.4 坑四重复调用get导致计数超标LeetCode 1095 的MountainArray接口有调用次数限制最多 100 次。我第一版代码里峰值查找和两次值查找之间互相重叠导致同一个下标被重复get测试用例多一点就直接超限。解决办法是函数调用时尽可能把相同的get结果存到局部变量里比如上面代码里的val mountainArr.get(mid)整个循环体内只用这一句后续比较都用val而不是再次调用get。虽然每次二分只有 O(log n) 次get三次加起来远小于 100但代码规范一点既省调用次数也让逻辑更清晰。另外写题的时候我还额外加了一点防御性设计值查找的前置判断。在进入二分前先检查target是否小于左区间的最小值arr[0]或大于左区间的最大值arr[peak]如果不在范围内就直接跳过左区间二分。这个剪枝不是必须的但可以减少无效的调用次数也是一种好习惯。5. 从 1095 延伸开这题背后的二分变体体系5.1 和旋转排序数组的对比如果你刷过 LeetCode 33“搜索旋转排序数组”会发现它和 1095 有某种相似感——都是“整体无序但分段有序”。旋转数组是由一个升序数组在某个点切割后交换顺序得到的比如[4, 5, 6, 7, 0, 1, 2]它也是“两段有序”只是有序段的方向都是升序而山脉数组两段方向相反。两类题的核心思想完全一致先通过某种方式找到“分界点”再在分界后的有序区间上做普通二分。旋转数组的分界点是“最小值位置”山脉数组的分界点是“峰顶”。找到了分界点整个问题就被化解为最基础的二分查找难度瞬间下降。所以 1095 的价值不只是它本身而是它让你理解了“分界点定向二分”这个组合套路。后面做搜索旋转数组、寻找峰值、寻找旋转数组最小值时很多代码结构都是互通的。刷一道题打通一类题这才是刷题效率最高的方式。5.2 二分查找的本质单调性与决策方向做题多了你会发现普通二分、找峰值、找旋转点、甚至是在有序矩阵里搜索这些问题的共性都是利用某种单调性质排除掉不可能包含答案的区间。普通二分里答案是一次比较后直接排除一半。找峰值里一次比较arr[mid]和arr[mid1]可以确定“峰顶在上坡方向还是下坡方向”从而排除另一半。旋转数组找最小值里比较arr[mid]和arr[right]可以确定“最小值在左半还是右半”。抓住这个本质你不需要背“模板”只需要在每一步都问自己我做这个比较能不能严格排除掉一部分区间如果能那这个方向就是对的如果不能说明比较对象选错了。这也是我在刷题过程中最大的体会二分不是“会背模板”就能解决的题型而是一种基于单调性的思维决策过程。题目一变比较对象、区间收缩方向、终止条件都要跟着变只有理解了“为什么”才能以不变应万变。5.3 如果面试官追问还能怎么优化1095 本身的解法已经是 O(log n)时间复杂度上没有再优化的空间了。但面试官可能会问一些延伸问题比如如果山脉数组中存在多个相等的 target你还能保证返回最小下标吗这个题本身的“先左后右”顺序已经保证了但你要能说清楚为什么。如果数组不满足“严格递增后严格递减”而是允许平台段相等元素你的峰值查找还成立吗答案是可能需要调整因为arr[mid] arr[mid1]时你无法判断方向。如果只允许最多调用 k 次get你的算法是否满足可以估算一下峰值查找大约log2(n)次两次值查找最多各log2(n)次总共约3 * log2(n)次。对n 10000来说大约 42 次左右远小于 100 的限制。能回答上这些追问说明你是真的理解了这题而不是背了个答案。6. 自己动手一套可复用的速查清单刷完 1095我记得最牢的是一套“山脉数组二分自查清单”这里分享给你第一步永远先找峰顶。没有峰顶位置后面两个区间搜索都无从谈起。峰值查找用left right区间收缩到一点就是峰值收缩时right mid而不是right mid - 1。左区间升序二分val target时left mid 1。右区间降序二分val target时right mid - 1。方向别写反。先搜左区间再搜右区间因为题目要最小下标。所有mid计算都用left (right - left) // 2。每次get结果存局部变量不要重复调用。如果你没法一眼看出方向在纸上画一个[1,2,3,4,5,3,1]的图把每次二分区间收窄的过程标出来跑一轮你就有感觉了。这套清单不只是为 1095 服务的。后面刷 162 寻找峰值、852 山脉数组的峰顶索引、33 搜索旋转排序数组时我都反复用这同一套思维框架几乎不需要额外适应直接套上就能写。二分的题目看似很多真正核心的骨架其实就这么几个把一道综合题吃透远胜过盲目刷十道简单题。最后再分享一个个人的小习惯每道二分的题 AC 之后我都会故意把“升序/降序”改错一次看自己能不能通过样例发现正确方向。这个“主动制造错误再修正”的练习法帮我建立了对二分方向更敏感的直觉比连续刷同类型十道题的效果还要好。你也可以试试。

山脉数组二分查找全解：三次二分破解 LeetCode 1095

相关推荐

哈夫曼编码文件压缩实战：从建树到位流避坑指南

ESXi驱动离线包安装避坑：版本串、依赖与验证

KB5004442 后 OPC Classic 连接失败：DCOM 拒绝激活排查与修复

更多资讯

C#日期时间处理避坑指南：DateTime与DateTimeOffset选型实战

进BIOS/UEFI的底层逻辑与跨平台通用进入方法论

Python语音控制无人机：从麦克风到Tello EDU指令的完整实战

Kali Linux命令行完全上手指南：从基础配置到高效排错

二维码纠错机制与修复实战：从里德-所罗门码到图像预处理

新媒体全链路运营工具选型常见问题解答

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？