欢迎阅读 欢迎来到「山脉数组的峰顶索引」题解之旅本文将带你从翻越一座单峰山脉找最高点这一直观场景出发深入理解二分查找二段性的精妙运用并掌握如何比较相邻元素判断上升/下降来定位峰顶下标。在开始之前建议你先了解题目背景这是 LeetCode 852 题给定山脉数组先严格递增后严格递减无重复返回峰顶元素的下标。本质上数组具有二段性——左半满足后一个更大右半不满足问题转化为二分找到二段性的分界点。明确学习目标掌握相邻元素比较式二分理解二段性判据与上升/下降段的划分并熟练处理峰顶在边界等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如arr [0,2,1,0]输出1arr [0,10,5,2]输出1。本文将从问题转化、相邻比较、区间收缩、返回结果到代码实现层层递进。即使你对二段性二分还不熟悉我们也会从哪边在上升就往哪边走这一直觉出发让你轻松抓住核心思想——比较邻居向高处收缩。现在让我们一起二分登顶找到山脉的最高点吧 ⛰️一.题目852. 山脉数组的峰顶索引 - 力扣LeetCode​二.做题思路一、问题分析前置分析题目要求在山脉数组先严格递增后严格递减长度 ≥ 3无重复中返回峰顶元素下标。关键约束存在唯一的峰顶arr[0] arr[1]且arr[n-2] arr[n-1]峰顶不在两端元素无重复。核心思路利用二段性——峰顶左侧满足arr[i] arr[i1]上升段右侧满足arr[i] arr[i1]下降段二分找分界点。二、算法策略二段性二分 · 相邻比较核心步骤初始化区间left 0、right n - 1。二分收敛while (left right)mid下取整left (right - left) / 2。相邻比较arr[mid] arr[mid 1]→ mid 在上升段峰顶在右半left mid 1arr[mid] arr[mid 1]→ mid 在下降段峰顶在左半含 midright mid。返回循环结束后left right即峰顶下标。示例执行过程arr [0,2,1,0]阶段leftrightmidarr[mid] vs arr[mid1]操作结果①0312 1 否 → 2 1下降段收缩右侧right1②0100 2上升段收缩左侧left1收敛11——返回 11arr [0,10,5,2]mid110 5 → right1mid00 10 → left1收敛于 1返回 1。均与题目一致。三、正确性说明简单版本二段性判据可靠山脉数组任意相邻对(arr[i], arr[i1])只有两种状态——上升峰顶左侧或下降峰顶右侧且状态单调变化一次判据arr[mid] arr[mid1]恰好识别二段性不会误判。收缩方向正确上升段丢弃左半含 mid下降段保留 mid 向左收敛峰顶始终在区间内单调收敛到唯一峰顶不漏解。终止性left mid 1与right mid下取整保证mid right均严格缩小不会死循环。无需校验题目保证山脉结构收敛点必为峰顶无需事后比较。四、实现细节边界防护初始化left 0、right (int)arr.size() - 1。边界防护题目保证n 3且峰顶不在两端arr[mid1]访问安全mid right恒成立n 1的退化输入会直接返回 0虽然题目不要求。复杂度时间 O(log n)每次排除一半区间空间 O(1)仅常数个变量。关键判断if (arr[mid] arr[mid 1]) left mid 1; else right mid;二段性收敛、while (left right)循环边界。五、返回值目标映射返回left峰顶下标对应题目返回峰顶元素的索引。三.代码class Solution { public: int peakIndexInMountainArray(vectorint arr) { int left 0; // 区间左端点 int right (int)arr.size() - 1; // 区间右端点 // 1. 二段性二分比较相邻元素判断 mid 在上升段还是下降段 while (left right) { int mid left (right - left) / 2; // mid 下取整配合 right mid if (arr[mid] arr[mid 1]) { left mid 1; // 上升段峰顶在右半丢弃左半含 mid } else { right mid; // 下降段峰顶在左半含 mid向左收敛 } } // 2. 收敛点即峰顶题目保证山脉结构无需校验 return left; } };四、易错点分析难点1比较的是arr[mid]与arr[mid1]而非targetif (arr[mid] arr[mid 1]) left mid 1; else right mid;传统二分比较arr[mid]与target本题没有 target比较对象是相邻元素。判据arr[mid] arr[mid1]回答的是mid 在峰顶的哪一侧——上升段在左、下降段在右。把判据换成比较 mid 与固定值或漏掉 mid1 的越界检查是本题最常见的错误方向。难点2为什么判据成立说明 mid 一定在上升段而非其他// 数组 0 2 1 0mid1 时 arr[1]2 arr[2]1 → 下降段 // 数组 0 2 5 3mid1 时 arr[1]2 arr[2]5 → 上升段二段性保证峰顶左侧所有相邻对都是上升右侧都是下降。因此只要arr[mid] arr[mid1]mid 必在峰顶左侧或恰好是峰顶前一位峰顶在[mid1, right]反之 mid 在峰顶右侧或恰为峰顶峰顶在[left, mid]。理解二段性的单调变化是正确推导收缩方向的关键。难点3收缩方向与 mid 取整的匹配int mid left (right - left) / 2; // 下取整 ... right mid; // 向左收缩保留 mid下降段执行right mid要求 mid下取整相邻区间right left 1时 mid 取 leftright mid使区间缩小不会死循环。若误用上取整如照抄 35 题模板相邻时 mid 取 rightright mid不缩小死循环。模板必须成套使用。难点4arr[mid 1]的越界风险while (left right) { int mid ...; if (arr[mid] arr[mid 1]) // 访问 mid1循环条件left right保证mid right ≤ n-1因此mid 1 ≤ n-1访问永远不越界。若把循环改成left right或 mid 上取整mid可能等于n-1甚至rightarr[mid1]将越界。这是把相邻比较写进错误循环条件时的高频 bug。五、流程图 闭幕 恭喜你完成了「山脉数组的峰顶索引」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题利用山脉数组的二段性先增后减通过比较arr[mid]与arr[mid1]来判断mid在上升段还是下降段。为什么只比较相邻元素就能确定峰顶的方位这背后的单调性依据是什么循环条件是left right最后返回left或right。为什么不需要像传统二分那样在循环后校验结果山脉数组的结构保证了什么本题要求时间复杂度 O(log n)。如果使用线性扫描找峰顶时间复杂度是多少在n 10^5时两种方法的效率差异有多大如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案相邻元素比较的核心依据是若arr[mid] arr[mid1]说明mid处于上升段峰顶一定在mid的右侧因为右侧还有更高的元素反之若arr[mid] arr[mid1]说明mid处于下降段峰顶一定在mid或其左侧。这是山脉数组“先增后减”的单调性决定的。无需校验因为题目保证数组是山脉数组峰顶一定存在且唯一二分收敛点必然就是峰顶不需要额外检查。线性扫描 O(n)而二分 O(log n)对于n10^5线性扫描 10^5 次二分只需约 17 次比较效率提升显著。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨