题目描述
思路解析
一句话答案：LeetCode 852 山脉数组：在先升后降的数组里求峰顶下标，用二分——单峰有保证，比中点和右邻谁大就知在上坡还是下坡，上坡收右、下坡收左逼向峰顶，时间 O(log n)、空间 O(1)。
山脉数组的峰顶，题目让你返回什么
给一个山脉数组 arr：它先严格递增爬到某个最高点，再严格递减下来，像一座只有一个尖的山。题目保证有且只有一个峰，要你返回峰顶元素的下标（不是峰顶的值）。题面 arr=[0,3,6,9,12,15,18,21,17,13,9,5,1]，21 排在第 7 格，所以返回 7。
一格格扫过去找拐点，慢在哪
从左往右一格格扫，找第一个 arr[i] 大于 arr[i+1] 的位置，那个 i 就是峰顶。可这要把整座山从山脚走到山顶，数组有 n 个数，峰若靠右就得比满将近 n 次，时间 O(n)。题目给的严格单峰、两侧都单调（左边只升、右边只降）的结构，被一格格扫白白浪费了。
单峰撑腰，比一下邻居就知道往哪走
靠的就是『先升后降、只有一个峰』这个保证。站在任意一格 mid，拿它和右邻居 arr[mid+1] 比：arr[mid] 小于右邻说明还在往上爬，峰顶必在它右边，左半连 mid 一起扔；arr[mid] 大于右邻说明已在下坡，峰顶在 mid 左边或就是它。一次比较就砍掉一半，正因为单峰，被丢的那半绝不藏更高的点。
上坡推左界、下坡收右界，循环为什么写 l 小于 r
用两个下标 l、r 圈住还没排除的范围，起初 l=0、r=n-1。每轮取中点 mid=(l+r)//2，和右邻 arr[mid+1] 比：上坡（arr[mid] 小于 arr[mid+1]）就让 l 跳到 mid+1，丢掉含 mid 的左半；下坡就让 r 收到 mid——是 mid 本身、不是 mid-1，因为 mid 自己可能就是峰顶，减一会把它一起丢。
循环条件写 while l 小于 r，收到 l==r 就停，范围只剩一格、它就是峰顶。这里有条不变量（每轮都成立的保证）：峰顶始终落在 [l,r] 内，每轮要么 l 前进、要么 r 后退，只缩不漏。
[0,3,6,…,21,…,1] 逼到第 7 格
起点 l=0、r=12。第一轮 mid=(0+12)//2=6，arr[6]=18 小于 arr[7]=21 是上坡，l 跳到 7。第二轮 l=7、r=12，mid=9，arr[9]=13 大于 arr[10]=9 是下坡，r 收到 9。第三轮 l=7、r=9，mid=8，arr[8]=17 大于 arr[9]=13 还是下坡，r 收到 8。第四轮 l=7、r=8，mid=7，arr[7]=21 大于 arr[8]=17 下坡，r 收到 7。此时 l=r=7，循环停，返回 7，即峰顶 21 的位置。
下坡那步减一，峰就被顺手丢了
最容易栽的是下坡那支写成 r=mid-1：mid 自己可能就是峰顶，减一把它排除，收敛的位置就偏左一格、错过真正的峰。循环条件也别写成 l 不大于 r——用 r=mid 收缩时一旦 l==r，mid 仍等于 l、区间缩不动，就成死循环。还有个隐蔽点：本题没有 target，别拿 arr[mid] 和某个目标值比，方向全由相邻两格谁大谁小定。
复杂度上，每轮砍掉一半，n 个数最多比约 log₂n 次，时间 O(log n)；只用 l、r、mid 三个下标，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住一句话：上坡就往右收（l = mid+1），下坡就往左收（r = mid）。每次砍掉一半，直到 l == r。
第一遍：13 个数的山脉。l 指最左、r 指最右。只要 l 还没和 r 撞上，就一直对半收紧区间。
当前范围 [0, 12] 的正中间是下标 6。接下来把它和右邻下标 7 比一比，判断在上坡还是下坡。
arr[6]=18 比右邻 arr[7]=21 小，说明这里还在往上爬。山顶一定在 6 右边，左边界要推到 mid+1。
把左半（含中点 6）整段灰掉排除，l 跳到 7。一次砍掉一半，范围缩到 [7, 12]。
当前范围 [7, 12] 的正中间是下标 9。接下来把它和右邻下标 10 比一比，判断在上坡还是下坡。
arr[9]=13 比右邻 arr[10]=9 大，说明已经开始下坡。山顶在 9 左边或正好就是它，右边界收到 mid。
把中点右边那段灰掉排除，r 收到 9（中点 9 自己可能就是峰顶，留下）。范围缩到 [7, 9]。
当前范围 [7, 9] 的正中间是下标 8。接下来把它和右邻下标 9 比一比，判断在上坡还是下坡。
arr[8]=17 比右邻 arr[9]=13 大，说明已经开始下坡。山顶在 8 左边或正好就是它，右边界收到 mid。
把中点右边那段灰掉排除，r 收到 8（中点 8 自己可能就是峰顶，留下）。范围缩到 [7, 8]。
当前范围 [7, 8] 的正中间是下标 7。接下来把它和右邻下标 8 比一比，判断在上坡还是下坡。
arr[7]=21 比右邻 arr[8]=17 大，说明已经开始下坡。山顶在 7 左边或正好就是它，右边界收到 mid。
把中点右边那段灰掉排除，r 收到 7（中点 7 自己可能就是峰顶，留下）。范围缩到 [7, 7]。
l 和 r 撞在下标 7，区间只剩一格。这一格 arr[7]=21 就是山顶，返回 7。
第二遍：换一座更矮的山。l 指最左、r 指最右。只要 l 还没和 r 撞上，就一直对半收紧区间。
当前范围 [0, 10] 的正中间是下标 5。接下来把它和右邻下标 6 比一比，判断在上坡还是下坡。
arr[5]=24 比右邻 arr[6]=20 大，说明已经开始下坡。山顶在 5 左边或正好就是它，右边界收到 mid。
把中点右边那段灰掉排除，r 收到 5（中点 5 自己可能就是峰顶，留下）。范围缩到 [0, 5]。
当前范围 [0, 5] 的正中间是下标 2。接下来把它和右邻下标 3 比一比，判断在上坡还是下坡。
arr[2]=8 比右邻 arr[3]=13 小，说明这里还在往上爬。山顶一定在 2 右边，左边界要推到 mid+1。
把左半（含中点 2）整段灰掉排除，l 跳到 3。一次砍掉一半，范围缩到 [3, 5]。
当前范围 [3, 5] 的正中间是下标 4。接下来把它和右邻下标 5 比一比，判断在上坡还是下坡。
arr[4]=19 比右邻 arr[5]=24 小，说明这里还在往上爬。山顶一定在 4 右边，左边界要推到 mid+1。
把左半（含中点 4）整段灰掉排除，l 跳到 5。一次砍掉一半，范围缩到 [5, 5]。
l 和 r 撞在下标 5，区间只剩一格。这一格 arr[5]=24 就是山顶，返回 5。
三个高频追问：越界为何安全、与普通二分的区别、以及为什么能用二分。
参考代码
def peakIndexInMountainArray(arr): l, r = 0, len(arr) - 1 while l < r: # 区间收成一点就停 mid = (l + r) // 2 if arr[mid] < arr[mid + 1]: # 上坡 l = mid + 1 # 峰顶在右，丢左半 else: # 下坡或正是峰顶 r = mid # 峰顶在左或就是它 return l # l == r 即峰顶复杂度
- 时间：O(log n)，每轮把搜索区间砍掉一半，最多比 log₂n 次
- 空间：O(1)，只用 l、r、mid 三个下标变量，不开额外数组
易错点
面试追问把动画讲成自己的话
追问为什么比较 arr[mid] 和 arr[mid+1] 不会越界？
追问这题和普通二分查找有什么不同？
追问能不能用 O(n) 线性扫？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
基于时间的键值存储
LeetCode 981 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题