题目描述
思路解析动画文字版
最直接:速度 = 1、2、3… 挨个试,第一个「能在 h 小时内吃完」的就是答案。最坏要试到 max(piles) 那么大,香蕉堆里有上亿根就试上亿次。但这里藏着规律——速度越大,耗时只会越短、绝不会忽长忽短,这种单调性正是二分的信号。
转折:与其挨个试速度,不如在速度区间 [1, max(piles)] 上二分。先写个判定函数 hours(k):逐堆 ⌈piles[i]/k⌉ 求和,得到吃完要几小时。不变量:hours(k) 随 k 增大单调递减。对中间速度 mid,hours(mid) ≤ h 说明够快、还能更慢(收右);大于 h 说明太慢(收左)——照样每步砍一半。
速度区间 [1, 11]:把候选速度排成一排(1~11),左指针 l=速度1,右指针 r=速度11。注意:二分的对象是速度,不是香蕉堆;每个速度够不够快,靠判定函数 hours 算。
第 1 轮 · 取 mid:中间下标取速度 6。先别急着收缩,用判定函数算算速度 6 到底要几小时。
第 1 轮 · 判定(够快):速度 6:每堆向上取整算小时,1+1+2+2 = 6 小时 ≤ 8,够快!它是个可行解,但说不定还能更慢,所以保留它、往左找更小的。
第 1 轮 · 收缩:速度 7~11(更快但更浪费)整段灰掉丢弃,r 收到 mid(不减 1,速度6 自己可能就是答案)。范围缩到速度 [1, 6]。
第 2 轮 · 取 mid:新范围 [1, 6],中间取速度 3。继续用判定函数算它要几小时。
第 2 轮 · 判定(太慢·负例):速度 3:1+2+3+4 = 10 小时,大于 8,超时了,不可行。说明速度 3 以及比它更慢的都不行,得加速——这一半要丢掉。
第 2 轮 · 收缩:速度 1、2、3(含 mid)都太慢,整段灰掉,l 跳到 mid+1(速度4)。范围缩到速度 [4, 6]。
第 3 轮 · 取 mid 并判定:范围 [4, 6],中间速度 5:1+2+2+3 = 8 小时,正好 ≤ 8,够快。保留它往左找,r 收到 mid(速度5)。范围缩到速度 [4, 5]。
第 4 轮 · 取 mid 并判定:范围 [4, 5],中间速度 4:也是 8 小时 ≤ 8,够快。r 收到 mid(速度4),此时 l == r,区间只剩速度 4,循环结束。
收敛 · 答案:l 和 r 撞在速度 4——这就是能在 8 小时内吃完的最小速度。再慢一档(速度3)就超时。
「求最小/最大的、满足某条件的值」,且条件随值单调,就能二分答案:x 的平方根、D 天送货都是它。
边界三连:三种边界先想清楚。
面试官常追问:三个高频追问,答法记牢。
参考代码
class Solution: def minEatingSpeed(self, piles, h): def hours(k): return sum((p + k - 1) // k for p in piles) # 各堆向上取整求和 l, r = 1, max(piles) while l < r: mid = (l + r) // 2 if hours(mid) <= h: r = mid # 够快 → 保留 mid,试更慢 else: l = mid + 1 # 太慢 → 提速 return l复杂度
- 时间复杂度:O(n log max),max=max(piles);二分 log(max) 次,每次判定 hours 扫一遍 n 堆
- 空间复杂度:O(1),只用 l、r、mid 几个变量,hours 现算不存表
可套用的代码模板
记住骨架:二分的是答案区间、核心是写对 check、合法时收右求最小。求最大值就把收缩方向反过来。
Python
# 求「满足条件的最小值」、且条件随值单调时套用def check(x): ... # 判定:速度/容量 x 行不行l, r = 最小可能, 最大可能while l < r: mid = (l + r) // 2 if check(mid): r = mid # 行,收右求更小 else: l = mid + 1 # 不行,加大return l易错点
面试追问把动画讲成自己的话
追问核心思路是什么?
追问为什么 r=mid 不减 1?
追问复杂度多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
寻找旋转排序数组中的最小值
LeetCode 153 · 中等 · 沿着 二分查找 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题