欢迎阅读 欢迎来到「寻找峰值」题解之旅本文将带你从在连绵起伏的山峦中任选一座山顶这一直观场景出发深入理解二段性二分的巧妙运用并掌握如何比较相邻元素判断坡向来定位任意一个峰值下标。在开始之前建议你先了解题目背景这是 LeetCode 162 题给定数组nums相邻元素不相等峰值定义为严格大于左右邻居的元素边界只需大于一侧邻居返回任意一个峰值下标。本质上数组必然存在峰值且二段性——左侧可能上升、右侧可能下降问题转化为二分收敛到任一分界点。明确学习目标掌握比较 nums[mid-1] 与 nums[mid] 的上取整模板理解与 852 题的镜像对称关系并熟练处理单元素、双元素与峰在边界等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,2,3,1]输出2nums [1,2,1,3,5,6,4]输出5或1。本文将从问题转化、坡向判断、区间收缩、返回结果到代码实现层层递进。即使你对二段性二分还不熟悉我们也会从往坡上走总能到山顶这一直觉出发让你轻松抓住核心思想——看坡向往高处走必达峰顶。现在让我们一起二分爬山找到任一座峰顶吧 ⛰️一.题目162. 寻找峰值 - 力扣LeetCode​二.做题思路一、问题分析前置分析题目要求在任意数组相邻元素不相等中返回任意一个峰值下标nums[i] nums[i-1]且nums[i] nums[i1]边界元素只需大于其唯一邻居。关键约束峰值必然存在全局最大值必是峰值返回任意一个即可相邻元素不相等。核心思路利用二段性与往上升方向走必达峰顶的性质用二分在 O(log n) 内收敛到任一个峰值。二、算法策略二段性二分 · 前邻比较核心步骤初始化区间left 0、right n - 1。二分收敛while (left right)mid上取整left (right - left 1) / 2保证mid 1使nums[mid-1]安全。前邻比较nums[mid - 1] nums[mid]→ 从mid-1到mid是下降峰值在左半right mid - 1nums[mid - 1] nums[mid]→ 从mid-1到mid是上升峰值在右半含 midleft mid。返回循环结束后left right即任一个峰值下标。示例执行过程nums [1,2,3,1]阶段leftrightmidnums[mid-1] vs nums[mid]操作结果①0322 3上升收缩左侧left2②2333 1下降收缩右侧right2收敛22——返回 22三、正确性说明简单版本峰值必然存在全局最大值一定满足峰值定义或边界峰值所以必有解无需处理无解分支。坡向判据可靠nums[mid-1] nums[mid]说明 mid 在下降段其左侧必有一个峰值沿上升方向回溯反之在上升段右侧必有一个峰值。判据不会漏掉可行方向。收缩方向正确下降段丢弃右半含 mid上升段保留 mid 向右收敛区间单调缩小且始终含至少一个峰值不会漏解。终止性right mid - 1与left mid上取整保证mid left均严格缩小不会死循环。四、实现细节边界防护初始化left 0、right (int)nums.size() - 1。边界防护上取整保证mid 1当left rightnums[mid-1]永不越界n 1时循环不进入直接返回 0该元素即峰值相邻元素不相等保证判据无歧义。复杂度时间 O(log n)每次排除一半空间 O(1)仅常数个变量。关键判断if (nums[mid - 1] nums[mid]) right mid - 1; else left mid;坡向收敛、while (left right)循环边界。五、返回值目标映射返回left任意一个峰值下标对应题目返回任何一个峰值所在位置。三.代码class Solution { public: int findPeakElement(vectorint nums) { int left 0; // 区间左端点 int right (int)nums.size() - 1; // 区间右端点 // 1. 二段性二分比较前邻元素判断 mid 在上升段还是下降段 while (left right) { // mid 上取整保证 mid 1nums[mid-1] 不越界且配合 left mid 防死循环 int mid left (right - left 1) / 2; if (nums[mid - 1] nums[mid]) { right mid - 1; // 下降段峰值在左半丢弃右半含 mid } else { left mid; // 上升段峰值在右半含 mid向右收敛 } } // 2. 收敛点即峰值峰值必然存在无需校验 return left; } };四、易错点分析难点1mid 必须上取整且这是nums[mid-1]安全的前提int mid left (right - left 1) / 2; // 上取整 if (nums[mid - 1] nums[mid])本模板含left mid向右收缩必须上取整否则相邻区间时 mid 取 leftleft mid卡死。同时上取整在left right时保证mid left 1 1因此nums[mid-1]永远不会访问下标 0 之前的元素。若误用下取整left mid死循环若强行访问nums[mid-1]mid0 时越界。难点2判据方向与 852 题是镜像对称的// 本题162比较 nums[mid-1] 与 nums[mid] → 上取整 // 852 题 比较 nums[mid] 与 nums[mid1] → 下取整852 题用arr[mid] arr[mid1]判上升并left mid 1本题用nums[mid-1] nums[mid]判下降并right mid - 1。两者判据互为镜像取整方向也互为镜像。把 852 的模板原样搬来下取整 比较 mid/mid1也能 AC 本题但把比较方向抄错如比较nums[mid] nums[mid-1]却配错收缩方向会收敛到错误的谷底。难点3为什么上升段保留 mid而不是跳过 midelse { left mid; // nums[mid-1] nums[mid]mid 可能是峰值必须保留 }nums[mid-1] nums[mid]只说明 mid 处于上升段mid本身可能就是峰值如[1,2,3]中 mid22 的右侧没有元素它就是边界峰值。若写成left mid 1直接跳过 mid可能漏掉恰好是峰值的 mid尤其峰在边界时。难点4边界元素峰值的处理无需特判return left; // n1 时 left0nums[0] 即峰值本题峰值定义对边界元素放宽只需大于唯一邻居。代码通过往上升方向走的性质隐式处理了边界峰值若数组单调二分会一路收敛到端点端点即峰值无需任何特判。若误以为必须写if (nums[0] nums[1]) return 0之类的特判反而画蛇添足、可能引入越界。五、流程图 闭幕 恭喜你完成了「寻找峰值」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考当nums[mid-1] nums[mid]时执行right mid - 1否则执行left mid。为什么这个分支逻辑能保证峰值一定在收缩后的区间内请从相邻元素的单调性角度解释。本题与山脉数组峰顶索引LC 852非常相似但峰值定义更宽泛可存在多个峰值且不要求先增后减。为什么 LC 852 中比较arr[mid]与arr[mid1]使用下取整而本题比较nums[mid-1]与nums[mid]使用上取整这两种写法的设计动机分别是什么时间复杂度为 O(log n)如果使用线性扫描找峰值时间复杂度是多少在n 10^5时两种方法的效率差异有多大延伸挑战如果问题改为寻找山谷局部最小值数组两端视为正无穷你如何修改比较逻辑和收敛方向如果数组是二维矩阵要求找出一个局部峰值即该元素大于其上下左右相邻元素你能否将一维二分的思想推广到二维请描述核心思路。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案分支逻辑依据若nums[mid-1] nums[mid]说明mid处于下降段左邻更大峰值在左半侧包括mid-1因此丢弃右半否则nums[mid-1] nums[mid]说明mid处于上升段右邻更大峰值在右半侧包括mid向右收敛。两种写法的设计动机LC 852 比较arr[mid]与arr[mid1]用下取整配合right mid因为山脉数组严格先增后减且峰值唯一本题比较nums[mid-1]与nums[mid]用上取整配合left mid因为峰值不唯一且两端视为负无穷上取整能保证mid向右靠拢更贴合“寻找任意峰值”的需求。线性扫描 O(n)二分 O(log n)n10^5时线性扫描需 10^5 次比较二分仅约 17 次效率显著提升。延伸挑战答案挑战1寻找局部最小值山谷只需将比较条件反置若nums[mid-1] nums[mid]谷底在左半right mid - 1否则谷底在右半left mid其余逻辑不变。挑战2二维找峰值可对行做二分找到中间行在该行中找最大值列然后比较该列上下元素若上邻更大则向上收缩行区间若下邻更大则向下收缩直到找到峰值时间复杂度 O(n log m) 或 O(m log n)。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨