企业官网建设流程全解析

👋 欢迎阅读

🎯 欢迎来到「山脉数组的峰顶索引」题解之旅！本文将带你从"翻越一座单峰山脉找最高点"这一直观场景出发，深入理解二分查找二段性的精妙运用，并掌握如何比较相邻元素判断上升/下降来定位峰顶下标。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 852 题，给定山脉数组（先严格递增后严格递减，无重复），返回峰顶元素的下标。本质上，数组具有二段性——左半满足"后一个更大"，右半不满足，问题转化为二分找到二段性的分界点。

• 明确学习目标：掌握相邻元素比较式二分，理解二段性判据与上升/下降段的划分，并熟练处理峰顶在边界等边界情况。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如arr = [0,2,1,0]输出1，arr = [0,10,5,2]输出1）。

本文将从问题转化、相邻比较、区间收缩、返回结果到代码实现，层层递进。即使你对二段性二分还不熟悉，我们也会从"哪边在上升就往哪边走"这一直觉出发，让你轻松抓住核心思想——比较邻居，向高处收缩。现在，让我们一起二分登顶，找到山脉的最高点吧！ ⛰️🎯

一.题目

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

​

二.做题思路

一、问题分析（前置分析）

• 题目要求：在山脉数组（先严格递增后严格递减，长度 ≥ 3，无重复）中返回峰顶元素下标。
• 关键约束：存在唯一的峰顶；arr[0] < arr[1]且arr[n-2] > arr[n-1]（峰顶不在两端）；元素无重复。
• 核心思路：利用二段性——峰顶左侧满足arr[i] < arr[i+1]（上升段），右侧满足arr[i] > arr[i+1]（下降段），二分找分界点。

二、算法策略（二段性二分 · 相邻比较）

核心步骤：

1. 初始化区间：left = 0、right = n - 1。
2. 二分收敛：while (left < right)，mid下取整（left + (right - left) / 2）。
3. 相邻比较：
   • arr[mid] < arr[mid + 1]→ mid 在上升段，峰顶在右半，left = mid + 1；
   • arr[mid] > arr[mid + 1]→ mid 在下降段，峰顶在左半（含 mid），right = mid。
4. 返回：循环结束后left == right即峰顶下标。

示例执行过程（arr = [0,2,1,0]）：

arr = [0,10,5,2]：mid=1，10 > 5 → right=1；mid=0，0 < 10 → left=1；收敛于 1，返回 1。均与题目一致。

三、正确性说明（简单版本）

• 二段性判据可靠：山脉数组任意相邻对(arr[i], arr[i+1])只有两种状态——上升（峰顶左侧）或下降（峰顶右侧），且状态单调变化一次，判据arr[mid] < arr[mid+1]恰好识别二段性，不会误判。
• 收缩方向正确：上升段丢弃左半（含 mid），下降段保留 mid 向左收敛，峰顶始终在区间内，单调收敛到唯一峰顶，不漏解。
• 终止性：left = mid + 1与right = mid（下取整保证mid < right）均严格缩小，不会死循环。
• 无需校验：题目保证山脉结构，收敛点必为峰顶，无需事后比较。

四、实现细节（边界防护）

• 初始化：left = 0、right = (int)arr.size() - 1。
• 边界防护：题目保证n >= 3且峰顶不在两端，arr[mid+1]访问安全（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(vector<int>& 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[mid+1]而非target

if (arr[mid] < arr[mid + 1]) left = mid + 1; else right = mid;

传统二分比较arr[mid]与target，本题没有 target，比较对象是相邻元素。判据arr[mid] < arr[mid+1]回答的是"mid 在峰顶的哪一侧"——上升段在左、下降段在右。把判据换成比较 mid 与固定值，或漏掉 mid+1 的越界检查，是本题最常见的错误方向。

难点2：为什么判据成立说明 mid 一定在"上升段"而非其他

// 数组 0 2 1 0：mid=1 时 arr[1]=2 > arr[2]=1 → 下降段 // 数组 0 2 5 3：mid=1 时 arr[1]=2 < arr[2]=5 → 上升段

二段性保证：峰顶左侧所有相邻对都是上升，右侧都是下降。因此只要arr[mid] < arr[mid+1]，mid 必在峰顶左侧（或恰好是峰顶前一位），峰顶在[mid+1, right]；反之 mid 在峰顶右侧或恰为峰顶，峰顶在[left, mid]。理解二段性的单调变化是正确推导收缩方向的关键。

难点3：收缩方向与 mid 取整的匹配

int mid = left + (right - left) / 2; // 下取整 ... right = mid; // 向左收缩保留 mid

下降段执行right = mid，要求 mid下取整：相邻区间（right = left + 1）时 mid 取 left，right = mid使区间缩小，不会死循环。若误用上取整（如照抄 35 题模板），相邻时 mid 取 right，right = mid不缩小，死循环。模板必须成套使用。

难点4：arr[mid + 1]的越界风险

while (left < right) { int mid = ...; if (arr[mid] < arr[mid + 1]) // 访问 mid+1

循环条件left < right保证mid < right ≤ n-1，因此mid + 1 ≤ n-1，访问永远不越界。若把循环改成left <= right或 mid 上取整，mid可能等于n-1甚至right，arr[mid+1]将越界。这是把"相邻比较"写进错误循环条件时的高频 bug。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「山脉数组的峰顶索引」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

• 本题利用山脉数组的二段性（先增后减），通过比较arr[mid]与arr[mid+1]来判断mid在上升段还是下降段。为什么只比较相邻元素就能确定峰顶的方位？这背后的单调性依据是什么？

• 循环条件是left < right，最后返回left（或right）。为什么不需要像传统二分那样在循环后校验结果？山脉数组的结构保证了什么？

• 本题要求时间复杂度 O(log n)。如果使用线性扫描找峰顶，时间复杂度是多少？在n = 10^5时两种方法的效率差异有多大？

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

• 相邻元素比较的核心依据是：若arr[mid] < arr[mid+1]，说明mid处于上升段，峰顶一定在mid的右侧（因为右侧还有更高的元素）；反之，若arr[mid] > arr[mid+1]，说明mid处于下降段，峰顶一定在mid或其左侧。这是山脉数组“先增后减”的单调性决定的。

• 无需校验：因为题目保证数组是山脉数组，峰顶一定存在且唯一，二分收敛点必然就是峰顶，不需要额外检查。

• 线性扫描 O(n)，而二分 O(log n)，对于n=10^5，线性扫描 10^5 次，二分只需约 17 次比较，效率提升显著。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨