第6章｜二分、堆与优先队列

Unit 05 · LeetCode #875

← Unit 04

仅本次页面有效

875

Koko Eating BananasBinary Search on Answer

数组没有排序，
但“速度是否可行”形成了单调答案空间。

本题不在 piles 中查找某个元素，而是在整数速度 1…max(piles) 中寻找第一个可行值。速度越大，完成所需时间不会增加，因此可行性从False切换到True后不会再变回False。

LeetCode #875 原题内容题面转述、答案空间与复杂度

题目要求

有 n 堆香蕉，第 i 堆有 piles[i] 根。珂珂选择一个整数速度 k，每小时选择一堆并最多吃掉 k 根；若该堆不足 k 根，则吃完后本小时不再吃其他堆。

返回能在 h 小时内吃完全部香蕉的最小整数速度。

class Solution: def minEatingSpeed( self, piles: List[int], h: int ) -> int: pass

约束

1 ≤ piles.length ≤ 10⁴；
piles.length ≤ h ≤ 10⁹；
1 ≤ piles[i] ≤ 10⁹。

官方示例

piles = [3,6,7,11], h = 8
输出：4

piles = [30,11,23,4,20], h = 5
输出：30

piles = [30,11,23,4,20], h = 6
输出：23

本页主方法

对速度区间 [1,max(piles)] 做Lower Bound二分。一次可行性检查扫描全部香蕉堆，时间复杂度 O(n log M)，其中 M=max(piles)；额外空间 O(1)。

答案空间

可能的速度不是数组下标，而是整数集合 1…max(piles)。二分搜索可以作用于任何有序候选空间。

可行性函数

feasible(k)判断速度k能否在h小时内完成任务。它把复杂任务压缩成一个True/False判断。

向上取整

一堆p根香蕉需要 ceil(p/k) 小时，因为不足一整小时的剩余仍占用一个完整小时。

最小可行边界

速度序列对应 False…False,True…True；答案是第一个True，而不是任意可行速度。

已恢复上次学习进度可继续当前阶段，也可清空并重新开始。

piles = [3,6,7,11]，h = 8拖动速度，观察每堆占用的完整小时

每小时速度 k4

1357911

当前可行性证据

速度4的总耗时为1+2+2+3=8，因此可行。

答案空间契约 最小可行速度始终位于当前候选区间[left,right]中。

一堆香蕉所需小时数 hours(pile,k) = ceil(pile/k) = (pile+k−1)//k

pile	速度k	小时数
总耗时		8

答案区间演化

当前速度mid4

总耗时8

feasible(mid)True

下一候选区间[1,4]

核心不变量

第一个满足总耗时≤h的速度始终位于当前候选区间中；可行速度的右侧全部可行。

速度为何具有单调性

速度增加时，每一项 ceil(pile/k) 都不会增加，因此总耗时不会增加，可行状态不会从True退回False。

速度候选数量11

已完成可行性检查0

当前总耗时8

距时限h0

当前结果未收敛

从模拟每个速度，升级为一次可行性判断排除半段

直接尝试速度1、2、3……需要最多M次检查；二分只需约log₂M次检查，每次检查扫描n堆。

三个常见错误会改变问题含义

答案空间二分的难点通常不在while模板，而在可行性函数、搜索边界和“可行后继续向左”三个环节。

错误一：使用pile // k

7根、速度4会得到1小时，但实际需要2小时。剩余3根仍占用下一完整小时。

错误二：mid可行就立即返回

速度6可行，但速度4也可行且更慢。题目要求第一个True，不是任意True。

错误三：right = mid - 1

在收敛式Lower Bound模板中，可行mid可能就是最小可行速度，必须执行right=mid保留它。

搜索边界可以从题意直接推出

最慢速度至少为1；速度达到最大香蕉堆大小后，每堆最多用1小时。由于h≥堆数，这一速度必然可行。

left = 1
速度不能为0

right = max(piles)
必然可行

h = len(piles)
答案必须是max(piles)

补全LeetCode提交代码最小可行速度Lower Bound

class Solution:

def minEatingSpeed(self, piles, h) -> int:

left =

right =

while :

mid =

hours = 0

for pile in piles:

hours +=

if hours <= h:

else:

return

提示会从“搜索对象”逐步推进到“可行性更新”，不会直接给出完整代码。

可提前终止可行性检查：累加过程中若 hours > h，已经可以判定当前速度不可行，不必继续扫描剩余香蕉堆；这不改变最坏复杂度，但能减少实际工作量。

代码—逐堆耗时—可行性带—答案区间联动示例[3,6,7,11], h=8

class Solution:
    def minEatingSpeed(self, piles, h):
        left = 1
        right = max(piles)
        while left < right:
            mid = left + (right-left)//2
            for pile in piles:
                hours += (pile+mid-1)//mid
            if hours <= h:
                right = mid
                left = mid + 1
        return left

播放后观察：速度6可行，保留[1,6]；速度3耗时10不可行，保留[4,6]；速度5可行，保留[4,5]；速度4可行并收敛。

完成代码联动后进入运载能力迁移只有主代码正确或完整播放轨迹后解锁；提示与答案空间骨架不会解锁。

迁移题：LeetCode #1011《在 D 天内送达包裹的能力》

复用“最小可行边界”的二分骨架，但重新设计可行性函数：包裹必须按给定顺序装船，容量不足时才能开始新的一天。

查看官方原题

先完成官方读题检查。

第6章 Unit 05 Skill卡

答案空间二分把“求最小满足约束的数值”转换为Lower Bound：先确定必不可能与必然可行的边界，再设计单调可行性函数，最后寻找False到True的第一次切换。

题号与题型#875｜答案空间二分＋最小可行边界

搜索对象速度k∈[1,max(piles)]，不要求出现在输入数组

可行性函数Σceil(pile/k)≤h

单调性k增大→总耗时不增→False…False,True…True

可行分支right=mid，保留mid寻找更小可行值

不可行分支left=mid+1，速度必须增大

复杂度时间O(n log M)，空间O(1)

常见错误使用向下取整；返回任意可行mid；搜索边界不可靠

推荐下一题#703 数据流中的第K大元素