刷题打卡到第125天碰上了一道值得单独写一篇的题LeetCode 162寻找峰值。说实话我第一次看到这道题的反应和大多数人一样——数组压根没排序凭什么用二分查找这不是开玩笑吗后来把官方题解翻来覆去看了好几遍又自己动手跑了十几个测试用例才真正想明白这题的精髓。今天就把这道题的来龙去脉从头到尾讲透题目规则里藏着什么玄机、无序数组凭什么能用二分、代码模板怎么写才能一次过以及我实际调试中踩过的几个边界大坑。如果你正在刷二分专题或者被“峰值”这类问题绕晕过这篇应该能帮你彻底打通。1. 峰值到底在找什么先抠清楚题目规则里的三个细节1.1 峰值定义比相邻元素都大边界元素只看一边题目给的定义是这样的峰值元素是严格大于相邻左右邻居的元素。注意“严格大于”这四个字它意味着不存在相等的情况这个特性在后面决定二分方向的时候非常重要后面我会专门讲到。对于数组中间的某个位置i成为峰值的条件是nums[i] nums[i-1]且nums[i] nums[i1]。但是对于数组的第一个元素和最后一个元素它们只有一边的邻居所以判断规则变成了第一个元素只要nums[0] nums[1]它就是一个峰值。最后一个元素只要nums[n-1] nums[n-2]它就是一个峰值。这个“边界只需比较一边”的规则是很多人在推导时容易忽略的点。它实际上是题目在暗示我们数组的边界外侧可以理解成负无穷。换句话说nums[-1] nums[n] -∞。有了这个约定其实所有位置的判断规则就统一了——每个位置只要比它两侧相邻的元素都大就是峰值。把边界视为负无穷是理解后面“峰值必然存在”这一结论的钥匙。1.2 关键保证相邻不相等到底给二分提供了什么题目里有一句容易被一带而过的话nums[i] ! nums[i1]对所有的i都成立。这句话初看只是防止出现歧义实际上它是整个二分解法成立的前提。试想一下如果相邻元素可以相等比如[1, 1, 1, 1]那么任何位置都不满足“严格大于邻居”的条件峰值不存在题目也就没有唯一解了。再比如[2, 2, 1]左边第一个 2 和第二 2 相等无法判断谁更大二分收缩区间时就会出现不可判定的情况。所以题目直接在源头把这个“不可判定”的选项堵死了每一步的比较只存在两种结果nums[mid] nums[mid1]或者nums[mid] nums[mid1]。没有第三种情况这使得我们可以用单个比较就能决定丢掉哪半边区间。1.3 题目要的是“一个”峰值不是“最大”的峰值LeetCode 162 的题目表述是“返回任何一个峰值即可”。这个“任何一个”给解题者松了大绑也是它能够用二分快速解决的原因之一。因为数组可能同时存在多个峰比如波浪形数组[1, 3, 2, 4, 1, 5]里3 和 4 以及 5 都是峰只要返回其中任意一个的下标就算通过。这一点和“找到数组最大值”有本质区别。找最大值必须遍历全数组因为最大值的定义是全局的你必须确认某个数比所有数都大才能下结论。而峰值是局部概念你只需要确认真某个数比它身边的两三个邻居大就够了。局部性意味着我们不需要看完全部数据这就给“只用对数次比较就能完成搜索”留出了空间。2. 无序数组为什么也能二分从“峰值必然存在”说起2.1 用爬坡模型理解从左侧出发一定会遇到峰顶很多人一提到二分查找脑子里想到的第一个前置条件就是“数组必须有序”。这个直觉没有错但它是针对“查找指定目标值”这种场景的。162 这道题要查的不是某个具体的值而是“位置”一个具有局部性质的特定位置类型。目标不同适用的约束自然也不同。怎么理解无序数组里也能二分我习惯用一个爬坡的比喻。想象你在一个起伏不平的山脉横截面上行走山脉的最左端和最右端都通向悬崖悬崖外是万丈深渊也就是负无穷。你现在站在左端点闭着眼睛往前走规则是“只要面前是上坡就继续走”。如果左端点右侧是下坡那你根本不用走脚下就是峰顶。如果左端点右侧是上坡那就往前走。由于整条山脉是有限的而且终点右侧就是悬崖这个上升趋势不可能永远持续下去。你总会在某个位置遇到“再往前走就是下坡”的情况那个位置就是一个峰顶。所以在这个模型里峰值一定存在而且从任意一端出发“顺着上坡走”一定能走到某个峰顶。这个结论不需要数组有序只需要边界外是负无穷以及山脉长度有限这两个前提。2.2 二分只是把爬坡过程加速了为什么可以放心丢掉一半爬山模型的结论告诉我们从左侧出发顺着上坡走一定能找到峰值但这样一步一步走最坏情况下要遍历整个数组时间复杂度是 O(n)。二分查找要做的事情就是给这个爬山过程装上“瞬移”能力——一次跳跃一半的距离。跳跃的方法是这样的取区间中点mid比较nums[mid]和nums[mid1]。如果nums[mid] nums[mid1]说明mid在爬坡坡顶在右侧那整个左半边区间包括mid都不可能是峰值所在的一侧直接丢掉区间收缩到[mid1, right]。如果nums[mid] nums[mid1]说明mid在下坡坡顶在左侧那整个右半边区间都可以丢掉区间收缩到[left, mid]。每次比较都能砍掉一半的搜索空间这正是二分的本质。整个过程循环下来区间不断缩小而且每一步都保证“峰值仍然在我们保留的区间里”最后剩下的那一个点就必然是峰值。这种“保证答案不丢”的区间收缩方式和有序数组二分里“保证目标值不丢”的收缩方式思路是一模一样的。2.3 三种特殊形态的数组全升、全降、单元素为了验证这个模型我建议动手把三类特殊情况跑一遍。第一种是全升数组比如[1, 2, 3, 4]。这种情况下最后一个元素就是峰值因为它大于它唯一的左邻居。二分的过程会一路触发nums[mid] nums[mid1]区间不断右移最后停在最后一个下标上。第二种是全降数组比如[4, 3, 2, 1]。这时候第一个元素就是峰值。二分的过程会一路触发nums[mid] nums[mid1]区间不断左移最后收敛到下标 0。第三种是单元素数组比如[5]。它没有邻居按题目定义它自己就是峰值。代码里left right 0二分循环根本不会进入直接返回 0。这三种情况跑通之后你对这个解法的信心会大很多。3. 核心洞察让 mid 和 mid1 说话而不是和 target 说话3.1 比较 nums[mid] 和 nums[mid1] 的几何含义普通二分查找里我们比较的是nums[mid]和目标值target据此判断“目标在左还是右”。在 162 这道题里没有target可以比取而代之的是nums[mid]与nums[mid1]的大小关系。这个比较的本质是在判断当前中点处在“上坡”还是“下坡”的哪一段上。我画了一个非常朴素的示意图来描述这件事峰顶 /\ / \ / \ / \ / \ 起点 终点外侧是负无穷当nums[mid] nums[mid1]时中点落在上坡段方向是向上走的那么峰顶一定在中点的右侧左半边全部丢弃。反之当nums[mid] nums[mid1]时中点落在下坡段说明峰顶在中点的左侧或者中点自己就是峰顶右半边丢弃。这里有一个很容易绕晕的点nums[mid] nums[mid1]是不是意味着mid自己就是峰值不一定。它只是说明mid处于一个下降沿真正的峰顶有可能在mid左侧的任意位置也有可能是mid自己。所以收缩区间时右边界取right mid保留mid位置不丢掉因为在进一步收缩的过程中mid仍然有可能是最终的答案。3.2 为什么只和右边比不比 mid-1 也不比 mid2很多初学者会问判断上坡下坡为什么只看nums[mid]和nums[mid1]这一对也可以看nums[mid-1]和nums[mid]啊甚至看nums[mid]和nums[mid2]行不行这里面有讲究。看nums[mid]和nums[mid1]是题目能保证“必定可比较”的一对相邻元素。如果看nums[mid-1]当mid 0时就会发生数组越界访问你需要额外处理mid是左边界的情况代码复杂度上升。如果看nums[mid2]当mid n-2时也会越界而且跳跃地比较两个不相邻的元素中间可能隔着峰谷判断出来的上坡下坡方向并不一定是全局趋势很可能把区间收缩引向错误方向。所以选择mid和mid1这一对比较最大的好处是天然规避了边界判断。在left right的循环条件下mid最坏情况取到right - 1那么mid 1最多取到right永远不会越界不需要额外写if分支。这个细节是让代码保持简洁的关键。3.3 多峰数组二分会稳定地找到哪一个峰当数组里有多个峰值时二分法的行为值得提前了解避免在测试时对自己的解法产生怀疑。比如[1, 3, 2, 4, 1, 5, 0]里面3、4、5 都是峰值。二分法会找到哪个答案是取决于中点的位置和每一次比较的方向。整个收缩过程像是一个“随机但确定”的爬山者——半路被放到某个点然后一直朝着上坡方向跳跃。最终它收敛到哪个峰取决于初始区间的中心位置以及每次比较的结果。但这道题不在乎你找到的是哪一个峰只要求合法即可。所以不需要纠结“为什么我的代码返回了第二个峰而不是第一个峰”只要返回的那个下标满足峰值定义就是正确解。4. 参考实现while (left right) 模板的三语言版本4.1 Python、Java、C 的参考解法先把最常用的写法放出来。这个写法核心是while (left right)配合mid left (right - left) // 2然后按上坡方向收缩。Python 版本from typing import List class Solution: def findPeakElement(self, nums: List[int]) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: left mid 1 else: right mid return leftJava 版本class Solution { public int findPeakElement(int[] nums) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { left mid 1; } else { right mid; } } return left; } }C 版本class Solution { public: int findPeakElement(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { left mid 1; } else { right mid; } } return left; } };三份代码的逻辑完全一致。核心就三行取中点、比较大小、收缩区间。剩下的交给循环自己去收敛。4.2 循环不变量每一步都保住“峰一定在区间里”要理解这段代码为什么正确不能只看它最终返回了一个数而是要关注循环不变量。这个版本的循环不变量是当前区间[left, right]内至少存在一个峰值。初始时整个数组[0, n-1]内必然存在峰值上一节已经证明了不变量成立。然后看每一步当nums[mid] nums[mid1]时mid处在上坡段峰顶不可能在[left, mid]这个左半段里所以我们把left推到mid 1新的区间[mid1, right]仍然包含至少一个峰不变量保持。当nums[mid] nums[mid1]时mid处在下坡段峰顶不可能在[mid1, right]右半段里把right收缩到mid新的区间[left, mid]仍然包含至少一个峰不变量保持。既然每一步都保证峰没有丢且区间长度严格递减循环必然结束。结束时left right此时区间只有一个元素而既然至少存在一个峰在这个区间里这个唯一的元素就是峰。这就是整个证明思路也是面试时你可以直接复述给考官的逻辑链条。4.3 循环为什么能终止以及 left 为什么正好落在峰上还有一个细节值得单独说明为什么是while (left right)而不是while (left right)这涉及到mid的计算和right mid的配合。在这个模板里mid left (right - left) // 2是向下取整的。当left right时mid一定小于right所以mid 1一定 ≤right不会越界。如果写成while (left right)当区间只剩两个元素时mid left如果进入else分支执行right mid区间的确会缩短但也有可能出现right不更新的情况当left right时仍进入循环导致死循环或者需要额外的返回判断。用left right收敛到一点代码最干净也最容易证明正确性。另外一个自然的问题是循环结束时为什么left恰好是峰顶因为收缩过程中保留的区间始终包含峰而且数组没有相等相邻元素所以当区间长度为 1 时这个唯一元素满足峰值的局部规则。它要么比右边大因为右边已经因为比较被排除要么是边界元素只需比左边大两种情况都成立。5. 与普通二分查找的区别排除法和爬坡法是两种思维5.1 一张表看清两类二分的差异我整理了下面这张对比表方便你快速看出普通二分和峰值二分的思维差异对比维度普通二分查找峰值二分查找前提条件数组有序无需有序相邻不相等边界外视为负无穷比较对象nums[mid]与targetnums[mid]与nums[mid1]收缩依据大小关系直接指示目标在哪半区上坡/下坡方向指示峰顶在哪半区循环结束left right或找到目标left right返回值目标值的下标若存在任意合法峰值的下标复杂度O(log n)O(log n)这张表能看出一个核心差异普通二分在做“消除法”——每次排除掉不可能包含目标值的一半峰值二分在做“爬坡法”——每次排除掉不可能包含峰值的一半但是依据的是“趋势方向”而不是“值的大小”。5.2 容易混淆的变体山脉数组峰值、旋转数组最小值刷到 162 之后你很快就会遇到一组长相相似但解法微调的题这里提前帮你做一个区分省得后面踩坑。第一类是山脉数组的峰顶索引比如 LeetCode 852。它的特征是数组先严格递增、后严格递减只有一个峰。解法一样可以用二分只不过因为峰唯一你可以用nums[mid] nums[mid1]判断在上升沿还是下降沿收缩逻辑和 162 几乎一致。第二类是寻找旋转排序数组的最小值比如 LeetCode 153。数组由有序数组旋转而来值的关系有一个断点。这里的二分依据是比较nums[mid]和nums[right]判断中点是在断点的左侧还是右侧。它和峰值二分的相似点在于“数组不是完全有序但仍可二分”但比较对象和收缩规则完全不同需要注意区分不能把 162 的模板硬套上去。第三类是二分答案型题目也就是热词里常出现的“爱吃香蕉的狒狒”那类题LeetCode 875。这类题是对“答案”进行二分而不是对数组下标二分每一轮用check(mid)判断当前速度是否可行。check函数写得好不好直接决定成败。这和 162 的“对下标二分”又是一层不同的思路。5.3 为什么不用三分查找有人可能会想既然要找峰顶那用三分查找每次把区间分成三份比较两个中点的值是不是更快理论上看三分查找确实常用在“单峰函数求极值”的场景比如山脉数组。但 162 并不是单峰数组它可能有很多峰。三分法在每一步都要比较两个位置mid1和mid2然后根据两者的高度关系判断丢弃哪一段。如果区间内存在多个峰三分法可能会因为两个中间点都落在同一侧斜坡上而做出错误判断丢掉包含峰顶的区间。更重要的是162 的二分只需要 O(log n) 次比较已经达到理论下限。三分每次保留 2/3 区间虽然也是对数级但常数更大而且前提条件更苛刻。所以直接用二分是最稳的解法不要为了炫技而用三分反而把自己绕进去。6. 实测中的坑与排查笔记我踩过的四个陷阱6.1 陷阱一不由自主地想先排序这道题最大的坑或者说最隐蔽的坑其实是思维惯性。我一开始写代码的时候第一反应是想调用sort()把数组排个序然后找最大值。幸好写用例的时候及时发现排序会彻底改变元素的位置关系返回的下标就不再是原数组中的峰值下标了。这个错误想法在评论区相当常见。要知道题目要的是“原数组中的峰值的下标”排序后一切索引都失去了意义。遇到无序数组的二分题先冷静几秒钟确认题目到底在找“值”还是在找“位置”。找值可能需要排序找位置则往往需要保留原始顺序。6.2 陷阱二while (left right) 的越界与死循环我在第一次按照普通二分的习惯写while (left right)时直接就报错了。原因是当left right时mid left此时访问nums[mid 1]如果mid正好是最后一个元素就会数组越界。即便没有越界这个循环也可能在收缩过程中出现left和right交叉但答案丢失的情况。解决方案就是一开始就用left right的模板。如果你非要用left right那么必须额外判断mid right的情况代码会多出好几个分支容易出错。实测下来left right配合right mid的模板最顺手建议直接把这个模板背下来。6.3 陷阱三用 nums[mid] nums[mid-1] 的边界爆炸还有一种常见写法是换成nums[mid] nums[mid - 1]作为判断条件同时尝试用三分或递归实现。这样做不是不行但必须非常小心mid 0的情况。在left right的循环中mid是可以取到 0 的比如数组只有两个元素时此时访问nums[mid - 1]直接就崩溃了。如果你特别喜欢这种写法就必须把循环改成while (left right)且把mid计算改成mid left (right - left 1) // 2这种向上取整的写法逻辑会绕不少。我的建议是不需要给自己加难度。nums[mid]和nums[mid1]这一对比较是天然安全的用它们就好。6.4 面试延伸考官想听你说什么如果把 162 作为面试题简单说对代码是不够的面试官通常会追问三个问题第一为什么用二分你要回答因为峰值是局部性质只需局部信息就能排除一半区间复杂度 O(log n) 优于 O(n) 遍历。第二为什么峰值一定存在你要回答边界外是负无穷上升趋势不可能无限持续所以至少有一个转折点。第三循环结束时为什么left就是答案你要回答循环不变量区间始终包含至少一个峰区间长度为 1 时该点必然是峰。把这三个问题回答顺了这道题才算真正吃透。比死记硬背代码重要得多。本来想再写一道类似的题做对比但篇幅已经足够长。个人体会是二分查找从来不应该是“有序数组的专属工具”它的本质是“在每一步都能利用既有信息排除一半选项”。162 这道题最大的价值就是把我们从“二分必须有序”的思维定式里拽了出来。如果你最近正在刷二分专题建议在 162 之后紧接着做 852、153 还有那道二分答案的 875把这几种二分的变体都过一遍。等到你能清晰说出每一道题“比较的是什么、收缩的依据是什么、循环不变量是什么”二分这个专题基本就稳了。我自己是在把这几题串起来做完之后才对“二分”这件事有了真正的手感。
刷题打卡到第125天碰上了一道值得单独写一篇的题LeetCode 162寻找峰值。说实话我第一次看到这道题的反应和大多数人一样——数组压根没排序凭什么用二分查找这不是开玩笑吗后来把官方题解翻来覆去看了好几遍又自己动手跑了十几个测试用例才真正想明白这题的精髓。今天就把这道题的来龙去脉从头到尾讲透题目规则里藏着什么玄机、无序数组凭什么能用二分、代码模板怎么写才能一次过以及我实际调试中踩过的几个边界大坑。如果你正在刷二分专题或者被“峰值”这类问题绕晕过这篇应该能帮你彻底打通。1. 峰值到底在找什么先抠清楚题目规则里的三个细节1.1 峰值定义比相邻元素都大边界元素只看一边题目给的定义是这样的峰值元素是严格大于相邻左右邻居的元素。注意“严格大于”这四个字它意味着不存在相等的情况这个特性在后面决定二分方向的时候非常重要后面我会专门讲到。对于数组中间的某个位置i成为峰值的条件是nums[i] nums[i-1]且nums[i] nums[i1]。但是对于数组的第一个元素和最后一个元素它们只有一边的邻居所以判断规则变成了第一个元素只要nums[0] nums[1]它就是一个峰值。最后一个元素只要nums[n-1] nums[n-2]它就是一个峰值。这个“边界只需比较一边”的规则是很多人在推导时容易忽略的点。它实际上是题目在暗示我们数组的边界外侧可以理解成负无穷。换句话说nums[-1] nums[n] -∞。有了这个约定其实所有位置的判断规则就统一了——每个位置只要比它两侧相邻的元素都大就是峰值。把边界视为负无穷是理解后面“峰值必然存在”这一结论的钥匙。1.2 关键保证相邻不相等到底给二分提供了什么题目里有一句容易被一带而过的话nums[i] ! nums[i1]对所有的i都成立。这句话初看只是防止出现歧义实际上它是整个二分解法成立的前提。试想一下如果相邻元素可以相等比如[1, 1, 1, 1]那么任何位置都不满足“严格大于邻居”的条件峰值不存在题目也就没有唯一解了。再比如[2, 2, 1]左边第一个 2 和第二 2 相等无法判断谁更大二分收缩区间时就会出现不可判定的情况。所以题目直接在源头把这个“不可判定”的选项堵死了每一步的比较只存在两种结果nums[mid] nums[mid1]或者nums[mid] nums[mid1]。没有第三种情况这使得我们可以用单个比较就能决定丢掉哪半边区间。1.3 题目要的是“一个”峰值不是“最大”的峰值LeetCode 162 的题目表述是“返回任何一个峰值即可”。这个“任何一个”给解题者松了大绑也是它能够用二分快速解决的原因之一。因为数组可能同时存在多个峰比如波浪形数组[1, 3, 2, 4, 1, 5]里3 和 4 以及 5 都是峰只要返回其中任意一个的下标就算通过。这一点和“找到数组最大值”有本质区别。找最大值必须遍历全数组因为最大值的定义是全局的你必须确认某个数比所有数都大才能下结论。而峰值是局部概念你只需要确认真某个数比它身边的两三个邻居大就够了。局部性意味着我们不需要看完全部数据这就给“只用对数次比较就能完成搜索”留出了空间。2. 无序数组为什么也能二分从“峰值必然存在”说起2.1 用爬坡模型理解从左侧出发一定会遇到峰顶很多人一提到二分查找脑子里想到的第一个前置条件就是“数组必须有序”。这个直觉没有错但它是针对“查找指定目标值”这种场景的。162 这道题要查的不是某个具体的值而是“位置”一个具有局部性质的特定位置类型。目标不同适用的约束自然也不同。怎么理解无序数组里也能二分我习惯用一个爬坡的比喻。想象你在一个起伏不平的山脉横截面上行走山脉的最左端和最右端都通向悬崖悬崖外是万丈深渊也就是负无穷。你现在站在左端点闭着眼睛往前走规则是“只要面前是上坡就继续走”。如果左端点右侧是下坡那你根本不用走脚下就是峰顶。如果左端点右侧是上坡那就往前走。由于整条山脉是有限的而且终点右侧就是悬崖这个上升趋势不可能永远持续下去。你总会在某个位置遇到“再往前走就是下坡”的情况那个位置就是一个峰顶。所以在这个模型里峰值一定存在而且从任意一端出发“顺着上坡走”一定能走到某个峰顶。这个结论不需要数组有序只需要边界外是负无穷以及山脉长度有限这两个前提。2.2 二分只是把爬坡过程加速了为什么可以放心丢掉一半爬山模型的结论告诉我们从左侧出发顺着上坡走一定能找到峰值但这样一步一步走最坏情况下要遍历整个数组时间复杂度是 O(n)。二分查找要做的事情就是给这个爬山过程装上“瞬移”能力——一次跳跃一半的距离。跳跃的方法是这样的取区间中点mid比较nums[mid]和nums[mid1]。如果nums[mid] nums[mid1]说明mid在爬坡坡顶在右侧那整个左半边区间包括mid都不可能是峰值所在的一侧直接丢掉区间收缩到[mid1, right]。如果nums[mid] nums[mid1]说明mid在下坡坡顶在左侧那整个右半边区间都可以丢掉区间收缩到[left, mid]。每次比较都能砍掉一半的搜索空间这正是二分的本质。整个过程循环下来区间不断缩小而且每一步都保证“峰值仍然在我们保留的区间里”最后剩下的那一个点就必然是峰值。这种“保证答案不丢”的区间收缩方式和有序数组二分里“保证目标值不丢”的收缩方式思路是一模一样的。2.3 三种特殊形态的数组全升、全降、单元素为了验证这个模型我建议动手把三类特殊情况跑一遍。第一种是全升数组比如[1, 2, 3, 4]。这种情况下最后一个元素就是峰值因为它大于它唯一的左邻居。二分的过程会一路触发nums[mid] nums[mid1]区间不断右移最后停在最后一个下标上。第二种是全降数组比如[4, 3, 2, 1]。这时候第一个元素就是峰值。二分的过程会一路触发nums[mid] nums[mid1]区间不断左移最后收敛到下标 0。第三种是单元素数组比如[5]。它没有邻居按题目定义它自己就是峰值。代码里left right 0二分循环根本不会进入直接返回 0。这三种情况跑通之后你对这个解法的信心会大很多。3. 核心洞察让 mid 和 mid1 说话而不是和 target 说话3.1 比较 nums[mid] 和 nums[mid1] 的几何含义普通二分查找里我们比较的是nums[mid]和目标值target据此判断“目标在左还是右”。在 162 这道题里没有target可以比取而代之的是nums[mid]与nums[mid1]的大小关系。这个比较的本质是在判断当前中点处在“上坡”还是“下坡”的哪一段上。我画了一个非常朴素的示意图来描述这件事峰顶 /\ / \ / \ / \ / \ 起点 终点外侧是负无穷当nums[mid] nums[mid1]时中点落在上坡段方向是向上走的那么峰顶一定在中点的右侧左半边全部丢弃。反之当nums[mid] nums[mid1]时中点落在下坡段说明峰顶在中点的左侧或者中点自己就是峰顶右半边丢弃。这里有一个很容易绕晕的点nums[mid] nums[mid1]是不是意味着mid自己就是峰值不一定。它只是说明mid处于一个下降沿真正的峰顶有可能在mid左侧的任意位置也有可能是mid自己。所以收缩区间时右边界取right mid保留mid位置不丢掉因为在进一步收缩的过程中mid仍然有可能是最终的答案。3.2 为什么只和右边比不比 mid-1 也不比 mid2很多初学者会问判断上坡下坡为什么只看nums[mid]和nums[mid1]这一对也可以看nums[mid-1]和nums[mid]啊甚至看nums[mid]和nums[mid2]行不行这里面有讲究。看nums[mid]和nums[mid1]是题目能保证“必定可比较”的一对相邻元素。如果看nums[mid-1]当mid 0时就会发生数组越界访问你需要额外处理mid是左边界的情况代码复杂度上升。如果看nums[mid2]当mid n-2时也会越界而且跳跃地比较两个不相邻的元素中间可能隔着峰谷判断出来的上坡下坡方向并不一定是全局趋势很可能把区间收缩引向错误方向。所以选择mid和mid1这一对比较最大的好处是天然规避了边界判断。在left right的循环条件下mid最坏情况取到right - 1那么mid 1最多取到right永远不会越界不需要额外写if分支。这个细节是让代码保持简洁的关键。3.3 多峰数组二分会稳定地找到哪一个峰当数组里有多个峰值时二分法的行为值得提前了解避免在测试时对自己的解法产生怀疑。比如[1, 3, 2, 4, 1, 5, 0]里面3、4、5 都是峰值。二分法会找到哪个答案是取决于中点的位置和每一次比较的方向。整个收缩过程像是一个“随机但确定”的爬山者——半路被放到某个点然后一直朝着上坡方向跳跃。最终它收敛到哪个峰取决于初始区间的中心位置以及每次比较的结果。但这道题不在乎你找到的是哪一个峰只要求合法即可。所以不需要纠结“为什么我的代码返回了第二个峰而不是第一个峰”只要返回的那个下标满足峰值定义就是正确解。4. 参考实现while (left right) 模板的三语言版本4.1 Python、Java、C 的参考解法先把最常用的写法放出来。这个写法核心是while (left right)配合mid left (right - left) // 2然后按上坡方向收缩。Python 版本from typing import List class Solution: def findPeakElement(self, nums: List[int]) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: left mid 1 else: right mid return leftJava 版本class Solution { public int findPeakElement(int[] nums) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { left mid 1; } else { right mid; } } return left; } }C 版本class Solution { public: int findPeakElement(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { left mid 1; } else { right mid; } } return left; } };三份代码的逻辑完全一致。核心就三行取中点、比较大小、收缩区间。剩下的交给循环自己去收敛。4.2 循环不变量每一步都保住“峰一定在区间里”要理解这段代码为什么正确不能只看它最终返回了一个数而是要关注循环不变量。这个版本的循环不变量是当前区间[left, right]内至少存在一个峰值。初始时整个数组[0, n-1]内必然存在峰值上一节已经证明了不变量成立。然后看每一步当nums[mid] nums[mid1]时mid处在上坡段峰顶不可能在[left, mid]这个左半段里所以我们把left推到mid 1新的区间[mid1, right]仍然包含至少一个峰不变量保持。当nums[mid] nums[mid1]时mid处在下坡段峰顶不可能在[mid1, right]右半段里把right收缩到mid新的区间[left, mid]仍然包含至少一个峰不变量保持。既然每一步都保证峰没有丢且区间长度严格递减循环必然结束。结束时left right此时区间只有一个元素而既然至少存在一个峰在这个区间里这个唯一的元素就是峰。这就是整个证明思路也是面试时你可以直接复述给考官的逻辑链条。4.3 循环为什么能终止以及 left 为什么正好落在峰上还有一个细节值得单独说明为什么是while (left right)而不是while (left right)这涉及到mid的计算和right mid的配合。在这个模板里mid left (right - left) // 2是向下取整的。当left right时mid一定小于right所以mid 1一定 ≤right不会越界。如果写成while (left right)当区间只剩两个元素时mid left如果进入else分支执行right mid区间的确会缩短但也有可能出现right不更新的情况当left right时仍进入循环导致死循环或者需要额外的返回判断。用left right收敛到一点代码最干净也最容易证明正确性。另外一个自然的问题是循环结束时为什么left恰好是峰顶因为收缩过程中保留的区间始终包含峰而且数组没有相等相邻元素所以当区间长度为 1 时这个唯一元素满足峰值的局部规则。它要么比右边大因为右边已经因为比较被排除要么是边界元素只需比左边大两种情况都成立。5. 与普通二分查找的区别排除法和爬坡法是两种思维5.1 一张表看清两类二分的差异我整理了下面这张对比表方便你快速看出普通二分和峰值二分的思维差异对比维度普通二分查找峰值二分查找前提条件数组有序无需有序相邻不相等边界外视为负无穷比较对象nums[mid]与targetnums[mid]与nums[mid1]收缩依据大小关系直接指示目标在哪半区上坡/下坡方向指示峰顶在哪半区循环结束left right或找到目标left right返回值目标值的下标若存在任意合法峰值的下标复杂度O(log n)O(log n)这张表能看出一个核心差异普通二分在做“消除法”——每次排除掉不可能包含目标值的一半峰值二分在做“爬坡法”——每次排除掉不可能包含峰值的一半但是依据的是“趋势方向”而不是“值的大小”。5.2 容易混淆的变体山脉数组峰值、旋转数组最小值刷到 162 之后你很快就会遇到一组长相相似但解法微调的题这里提前帮你做一个区分省得后面踩坑。第一类是山脉数组的峰顶索引比如 LeetCode 852。它的特征是数组先严格递增、后严格递减只有一个峰。解法一样可以用二分只不过因为峰唯一你可以用nums[mid] nums[mid1]判断在上升沿还是下降沿收缩逻辑和 162 几乎一致。第二类是寻找旋转排序数组的最小值比如 LeetCode 153。数组由有序数组旋转而来值的关系有一个断点。这里的二分依据是比较nums[mid]和nums[right]判断中点是在断点的左侧还是右侧。它和峰值二分的相似点在于“数组不是完全有序但仍可二分”但比较对象和收缩规则完全不同需要注意区分不能把 162 的模板硬套上去。第三类是二分答案型题目也就是热词里常出现的“爱吃香蕉的狒狒”那类题LeetCode 875。这类题是对“答案”进行二分而不是对数组下标二分每一轮用check(mid)判断当前速度是否可行。check函数写得好不好直接决定成败。这和 162 的“对下标二分”又是一层不同的思路。5.3 为什么不用三分查找有人可能会想既然要找峰顶那用三分查找每次把区间分成三份比较两个中点的值是不是更快理论上看三分查找确实常用在“单峰函数求极值”的场景比如山脉数组。但 162 并不是单峰数组它可能有很多峰。三分法在每一步都要比较两个位置mid1和mid2然后根据两者的高度关系判断丢弃哪一段。如果区间内存在多个峰三分法可能会因为两个中间点都落在同一侧斜坡上而做出错误判断丢掉包含峰顶的区间。更重要的是162 的二分只需要 O(log n) 次比较已经达到理论下限。三分每次保留 2/3 区间虽然也是对数级但常数更大而且前提条件更苛刻。所以直接用二分是最稳的解法不要为了炫技而用三分反而把自己绕进去。6. 实测中的坑与排查笔记我踩过的四个陷阱6.1 陷阱一不由自主地想先排序这道题最大的坑或者说最隐蔽的坑其实是思维惯性。我一开始写代码的时候第一反应是想调用sort()把数组排个序然后找最大值。幸好写用例的时候及时发现排序会彻底改变元素的位置关系返回的下标就不再是原数组中的峰值下标了。这个错误想法在评论区相当常见。要知道题目要的是“原数组中的峰值的下标”排序后一切索引都失去了意义。遇到无序数组的二分题先冷静几秒钟确认题目到底在找“值”还是在找“位置”。找值可能需要排序找位置则往往需要保留原始顺序。6.2 陷阱二while (left right) 的越界与死循环我在第一次按照普通二分的习惯写while (left right)时直接就报错了。原因是当left right时mid left此时访问nums[mid 1]如果mid正好是最后一个元素就会数组越界。即便没有越界这个循环也可能在收缩过程中出现left和right交叉但答案丢失的情况。解决方案就是一开始就用left right的模板。如果你非要用left right那么必须额外判断mid right的情况代码会多出好几个分支容易出错。实测下来left right配合right mid的模板最顺手建议直接把这个模板背下来。6.3 陷阱三用 nums[mid] nums[mid-1] 的边界爆炸还有一种常见写法是换成nums[mid] nums[mid - 1]作为判断条件同时尝试用三分或递归实现。这样做不是不行但必须非常小心mid 0的情况。在left right的循环中mid是可以取到 0 的比如数组只有两个元素时此时访问nums[mid - 1]直接就崩溃了。如果你特别喜欢这种写法就必须把循环改成while (left right)且把mid计算改成mid left (right - left 1) // 2这种向上取整的写法逻辑会绕不少。我的建议是不需要给自己加难度。nums[mid]和nums[mid1]这一对比较是天然安全的用它们就好。6.4 面试延伸考官想听你说什么如果把 162 作为面试题简单说对代码是不够的面试官通常会追问三个问题第一为什么用二分你要回答因为峰值是局部性质只需局部信息就能排除一半区间复杂度 O(log n) 优于 O(n) 遍历。第二为什么峰值一定存在你要回答边界外是负无穷上升趋势不可能无限持续所以至少有一个转折点。第三循环结束时为什么left就是答案你要回答循环不变量区间始终包含至少一个峰区间长度为 1 时该点必然是峰。把这三个问题回答顺了这道题才算真正吃透。比死记硬背代码重要得多。本来想再写一道类似的题做对比但篇幅已经足够长。个人体会是二分查找从来不应该是“有序数组的专属工具”它的本质是“在每一步都能利用既有信息排除一半选项”。162 这道题最大的价值就是把我们从“二分必须有序”的思维定式里拽了出来。如果你最近正在刷二分专题建议在 162 之后紧接着做 852、153 还有那道二分答案的 875把这几种二分的变体都过一遍。等到你能清晰说出每一道题“比较的是什么、收缩的依据是什么、循环不变量是什么”二分这个专题基本就稳了。我自己是在把这几题串起来做完之后才对“二分”这件事有了真正的手感。
