§1
题目描述
给定一个长度为 n 的整数 山脉 数组 arr ,其中的值递增到一个 峰值元素 然后递减。 返回峰值元素的下标。 你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
arr = [1,3,5,6,4,2,0]
输出 = 3
§2
思路解析动画文字版
下面 9 步动画会按主解代码推进,而不是泛泛讲题型。
1. 读入山脉数组:山脉数组先升后降,要找峰顶下标。本例 [1,3,5,6,4,2,0],峰是 6(下标 3)。
2. 初始化 l,r:二分边界 l=0、r=6。利用单调性:比较 arr[mid] 与 arr[mid+1] 判断在上坡还是下坡。
3. 第1轮 mid=3:mid = (0+6)//2 = 3。比较 arr[3]=6 与 arr[4]=4。
4. 下坡 → r=3:arr[3]=6 不小于 arr[4]=4,mid 处于峰顶或下坡,峰在 mid 或其左边,r = mid = 3。
5. 第2轮 mid=1:mid = (0+3)//2 = 1。比较 arr[1]=3 与 arr[2]=5。
6. 上坡 → l=2:arr[1]=3 小于 arr[2]=5,还在上坡,峰在右边,l = mid+1 = 2。
7. 第3轮 mid=2:mid = (2+3)//2 = 2。比较 arr[2]=5 与 arr[3]=6。
8. 上坡 → l=3:arr[2]=5 小于 arr[3]=6,仍在上坡,l = mid+1 = 3。
9. 收敛, 返回峰顶 3:l = r = 3,循环结束。峰顶下标是 3(值 6)。二分每轮砍半,O(log n)。
记住这题的代码骨架:题意约束先落到状态变量,再用循环或递归维护它。
§3
参考代码
class Solution: def peakIndexInMountainArray(self, arr): l = 0 r = len(arr) - 1 while l < r: mid = (l + r) // 2 if arr[mid] < arr[mid + 1]: l = mid + 1 else: r = mid return l看懂代码不等于写得出。盖住上面,自己默写一遍试试。卡在哪一行说不清,就点右下角问小欧。
§4
复杂度
- 时间复杂度:O(log n),每次缩半
- 空间复杂度:O(1),只用指针
§5
易错点
✗ 错误写法:访问 mid-1 和 mid+1 边界复杂
✓ 正确写法:只比较 mid 和 mid+1
l 小于 r 时 mid+1 不会越界
✗ 错误写法:上坡时 r=mid
✓ 正确写法:上坡时 l=mid+1
峰值一定在右侧
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
下一题 · 二分套路 12/14
→基于时间的键值存储
LeetCode 981 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路?去图解算法专题