Koko 吃香蕉为什么能二分速度？如何证明可行性单调？

简化版

Koko 吃香蕉二分的是“速度 k”，不是数组下标。速度越大，吃完所需时间越少；如果速度 k 能在 h 小时内吃完，那么所有更大的速度也能吃完，所以可行性满足单调性。对 k 在 [1, max(piles)] 上二分，计算 sum(ceil(pile / k))，找第一个满足 hours <= h 的最小速度。

详细版

这题是典型二分答案：答案空间是吃香蕉速度 k，范围从 1 到最大堆香蕉数。判断函数是 can(k)：以速度 k 吃完所有堆是否不超过 h 小时。每堆耗时是向上取整 (pile + k - 1) / k，因为一小时只能吃同一堆，剩一点也要占一小时。

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, h, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

boolean canFinish(int[] piles, int h, int k) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;
    return hours <= h;
}

复杂度是 O(n log M)，M 是最大堆大小。面试重点是讲清楚单调性、上界为什么是 max(piles)、以及向上取整不能写成普通除法。

完整版教学

一、这题为什么不是在数组里找数

普通二分是在有序数组中找目标值，而 Koko 这题没有一个显式有序数组。它要求的是最小吃香蕉速度，速度 k 可以取 1 到 max(piles) 之间的整数。这个整数区间虽然不是输入数组，但它本身是有序的，且每个速度都能被判定为“可行”或“不可行”。

例如 piles=[3,6,7,11]、h=8，速度 1 明显不行，速度 11 一定可以，因为每堆最多一小时。把每个速度标成是否可行，会出现一段 false 后接一段 true 的结构。二分答案就是在这个结构上找第一个 true。

k:       1  2  3  4  5  6  ...
can(k):  F  F  F  T  T  T  ...
目标：找最左边的 T

二、单调性来自“速度越快，耗时越少”

判断函数 can(k) 的核心是总耗时。速度 k 越大，每一堆需要的小时数 ceil(pile/k) 就不会增加，所以总耗时也不会增加。于是如果某个速度 k 可行，所有更大的速度都可行；如果某个速度不可行，所有更小的速度也不可行。

带数字走一遍：对 11 根香蕉，速度 3 需要 ceil(11/3)=4 小时，速度 4 需要 ceil(11/4)=3 小时，速度 6 需要 ceil(11/6)=2 小时。速度增加只会让耗时持平或下降，这就是二分能排除半边的原因。

速度 k	3 根	6 根	7 根	11 根	总小时
3	1	2	3	4	10
4	1	2	2	3	8
5	1	2	2	3	8

记忆钩子：二分答案先问“答案越大，限制是更容易满足还是更难满足”，Koko 是速度越大越容易满足。

三、边界为什么是 1 到 max(piles)

下界是 1，因为速度为 0 没意义，且每小时至少吃 1 根才可能前进。上界可以取 max(piles)，因为速度达到最大堆大小后，每一堆最多一小时吃完，再大也不会让单堆耗时低于 1 小时。也就是说超过 max(piles) 没有必要。

这不是拍脑袋取边界，而是根据答案的物理含义缩小搜索空间。若最大堆是 11，速度 12 和速度 11 的效果一样：11 那堆都是一小时，其他堆也都是一小时。因此 [1, max] 一定包含最优解，且不会漏。

lo = 1
hi = max(piles)
答案一定在 [lo, hi] 内

四、向上取整是最容易错的细节

每堆香蕉必须完整吃完，剩下一根也要额外占一小时，所以耗时是向上取整。整数代码里常用 (pile + k - 1) / k。例如 pile=7,k=3，普通除法得到 2，但实际需要 3 小时；公式 (7+3-1)/3 = 9/3 = 3 正好。

如果数据范围较大，累加总小时要用 long，因为 piles 数量多时总和可能超过 int。虽然很多平台 h 是 int，但中间累加溢出会导致可行性判断反向，二分就会收敛到错误答案。

long hours = 0;
for (int p : piles) {
    hours += (p + k - 1) / k;
}

五、为什么用 lower_bound 模板

我们要找的是第一个可行速度，也就是最左 true。因此适合使用半开或闭区间的 lower_bound 思路。这里用闭区间收缩到单点：while (lo < hi)，若 mid 可行，说明答案可能是 mid 或更小，令 hi = mid；若 mid 不可行，答案只能更大，令 lo = mid + 1。

这个写法的好处是循环结束时 lo == hi，它就是最小可行速度。不要在可行时直接返回 mid，因为 mid 只是一个可行解，不一定最小。二分答案题常见追问就是“为什么不是找到一个可行就停”。

can(mid) == true  -> [lo, mid] 里继续找更小可行
can(mid) == false -> [mid+1, hi] 里找可行

六、和其他二分答案题的共性

Koko、运送包裹、分割数组最大值这类题都是“最小化某个上限”。它们的共同套路是：猜一个答案 x，然后问“x 是否足够大，能满足约束”。如果 x 足够大，更大的 x 也足够；如果 x 不够，更小的 x 也不够，于是形成单调布尔数组。

区别只在 can(x) 怎么写。Koko 的 can(k) 是按速度计算总小时；运包的 can(capacity) 是按容量模拟天数；分割数组的 can(maxSum) 是按最大段和模拟段数。只要能证明单调性，二分就不是硬套模板。

题目	二分对象	可行性含义
Koko 吃香蕉	速度 k	总小时不超过 h
运送包裹	船容量 cap	天数不超过 D
分割数组最大值	最大段和 limit	分段数不超过 m

七、常见误区与追问

误区：在 piles 数组上二分。 piles 是否有序不重要，真正有序的是速度答案空间。
误区：每堆耗时用普通除法。 剩余香蕉也占一小时，必须向上取整。
误区：找到可行速度就返回。 题目要求最小速度，要继续往左找第一个可行值。
追问：为什么上界是 max(piles)？ 速度超过最大堆不会让任何一堆低于 1 小时，收益为零。
追问：复杂度怎么写？ 每次判断扫 n 堆，二分速度范围 1 到 M，所以是 O(n log M)。
追问：如何识别这是二分答案？ 看到“最小速度/容量/最大值”且可行性随答案单调变化，就优先考虑二分答案。

八、加强记忆

Koko 的主线是“速度答案空间 + 可行性单调”。先定范围 [1, max(piles)]，再写 can(k) 计算向上取整总小时。can(mid) 为真就往左压，假就往右走，最终得到最小可行速度。记住它不是找数组元素，而是找第一个让约束成立的速度。

简化版

详细版