Koko 吃香蕉问题：从暴力枚举到二分答案的单调性建模（LeetCode 875 解析）

Koko 吃香蕉问题：从暴力枚举到二分答案的单调性建模（LeetCode 875 解析）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 LeetCode 875「Koko Eating Bananas（吃香蕉）」为对象，讲解如何从逐一试速的暴力解法过渡到基于答案空间二分（binary search on answer）的最优解。读完你将掌握：如何识别“可行域单调”这一可二分的前提、如何正确划定速度上下界、向上取整计时的正确写法，以及整数溢出等典型陷阱——这些技巧同样适用于“容量分配”“时间限制下求最小速率”一类问题。仓库中该题已有 Python、Java、C++、JavaScript、Go、Rust 等 12 种语言实现，均可作为对照参考。

问题定义

守卫离开h小时，香蕉堆为数组piles。Koko 每小时选择一堆吃，吃k根（不足k根则吃完该堆）；某堆吃完后她才会换下一堆。求满足“h小时内吃完所有香蕉”的最小整数速度k。

关键性质（后面推导的基础）：速度越大，总耗时单调不减地变小。只要k = max(piles)，每堆至多一小时即可吃完，总耗时至多为堆数，而题目保证存在合法解，因此答案必然落在[1, max(piles)]区间内。

前置知识

按 articles/eating-bananas.md 的 Prerequisites 一节，本题需要三个基础：

• Binary Search（二分搜索）：最优解不是对数据排序后找值，而是对“答案空间”（速度的取值区间）二分，这是本文档的核心思想；
• Search Space Reduction（搜索空间缩减）：识别单调性质，确认“速度→总耗时”是单调递减函数，且判定条件totalTime <= h在答案处由假变真，才可以用二分；
• Ceiling Division（向上取整）：每堆耗时必须向上取整——哪怕只剩 1 根，Koko 也会占用一整小时（吃满后停止，且题目规定每小时只能吃同一堆）。

解法一：暴力枚举所有速度

思路

从speed = 1开始逐一尝试：对每个速度，累加每堆的ceil(pile / speed)得到总耗时，第一个满足totalTime <= h的速度即为答案。

算法步骤

1. 令speed = 1；
2. 对每个速度，计算所有堆的ceil(pile / speed)之和；
3. 若总和<= h，返回当前速度；
4. 否则speed += 1重复。

代码示例

文档中给出了 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的暴力实现，此处以 Python 为例：

class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: speed = 1 while True: totalTime = 0 for pile in piles: totalTime += math.ceil(pile / speed) if totalTime <= h: return speed speed += 1 return speed

C++ 版本展示了不依赖浮点的向上取整写法：

class Solution { public: int minEatingSpeed(vector<int>& piles, int h) { int speed = 1; while (true) { long long totalTime = 0; for (int pile : piles) { totalTime += (pile + speed - 1) / speed; // 整数上取整 } if (totalTime <= h) { return speed; } speed++; } } };

复杂度

• 时间复杂度：$O(m \times n)$，其中 $n$ 是piles长度，$m$ 是单堆最大香蕉数（最坏要尝试到m才停）；
• 空间复杂度：$O(1)$。

当h较小、答案接近max(piles)时，暴力法要线性扫过几乎整个区间，这就是二分优化的动机。

解法二：对答案空间二分

直觉与单调性论证

总耗时函数 $T(k) = \sum_i \lceil piles_i / k \rceil$ 关于 $k$ 单调不增。于是判定函数 $P(k): T(k) \le h$ 在速度轴上呈现“先假后真”的分界形态：

k: 1 2 3 4 5 6 ... max(piles) P(k): F F F T T T ... T ↑ 答案 = 最靠左的 T

这正是“找左边界”的标准二分模板：若mid可行，记录它并把right压到mid - 1继续向左找；否则把left抬到mid + 1。

边界划定

• left = 1：最小可能速度（不能为 0，否则除零）；
• right = max(piles)：速度超过最大堆毫无收益——更大的堆本来就一小时吃完，更小的堆耗时只会更少。

文档 Common Pitfalls 一节特别指出，把上界设成sum(piles)是常见错误：区间虽然仍然正确，但比必要的更大，白白增加二分迭代次数。

算法步骤

1. 设搜索区间left = 1，right = max(piles)，并初始化res = right；
2. 当left <= right：取mid = (left + right) // 2作为待测速度，计算总耗时；
3. 若总耗时<= h：该速度可行，记录res = mid，搜左半区right = mid - 1；
4. 否则：速度太慢，搜右半区left = mid + 1；
5. 循环结束后返回res，即最小可行速度。

Python 实现

class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: l, r = 1, max(piles) res = r while l <= r: k = (l + r) // 2 totalTime = 0 for p in piles: totalTime += math.ceil(float(p) / k) if totalTime <= h: res = k r = k - 1 else: l = k + 1 return res

复杂度

• 时间复杂度：$O(n \times \log m)$，外层二分 $\log m$ 轮，每轮扫一遍 $n$ 个堆；
• 空间复杂度：$O(1)$。

对比暴力法的 $O(m \times n)$，当m很大时（题目约束下可达 $10^9$）优势显著。

仓库中的多语言实现对照

仓库为该题提供了 12 份语言实现，它们与文档的算法骨架一致，但在工程细节上各有取舍，值得逐一比对：

从源码结构看，这些实现体现了三种常见的二分写法变体：①闭区间 +res记录（Python/C++/Rust/文档版）；②半开区间left < right直接收敛（Java/JavaScript）；③用固定大上界代替max(piles)（Go）。三种写法正确性等价，选择哪种取决于团队习惯——文档采用的是第一种，边界语义最直观。

常见陷阱（Common Pitfalls）

文档专设 Pitfalls 一节总结了三个高频错误，均有多语言代码佐证。

1. 用整除代替向上取整

Koko 吃不满一小时也不会“省时间”——只要还有剩余就占满整小时，因此必须向上取整：

# 错误：整除向下取整 totalTime += pile // speed # 正确：向上取整 totalTime += math.ceil(pile / speed) # 或不依赖 math 模块的整数写法： totalTime += (pile + speed - 1) // speed

C++ 版 cpp/0875-koko-eating-bananas.cpp 用浮点ceil实现，Rust 版 rust/0875-koko-eating-bananas.rs 用(x - 1) / m + 1整数实现，两者殊途同归。注意浮点ceil对极大整数（接近 $2^{53}$）存在精度风险，竞赛与生产代码更推荐纯整数上取整。

2. 二分边界设错

# 错误：从 0 开始会除零 l = 0 # 错误：上界无谓放大（正确但区间过大） r = sum(piles) # 正确边界 l, r = 1, max(piles)

下界为 0 会直接引发除零异常；上界用sum(piles)虽然逻辑正确，但会把二分轮数放大到 $\log(\text{sum})$。go/0875-koko-eating-bananas.go 则取了第三个极端——直接用题目约束 $10^9$ 作上界，正确性依赖题目给定的数据范围，脱离题目约束时不如max(piles)稳健。

3. 总耗时的整数溢出

对每堆耗时求和时，n与m均很大时总和可能超过 32 位整型上限：

// 错误：可能溢出 int totalTime = 0; // 正确：使用 long long totalTime = 0;

仓库实现对此处理一致：Java 用long totalTime，C++ 用long long（暴力版）/long int（二分版），Rust 用i64累加。跨语言读者迁移代码时，这一点最容易漏掉。

小结

• 本题的建模关键是发现“速度→耗时”的单调性，把优化问题转化为“有序判定序列上找第一个真值”的分界问题；
• 最优解为 $O(n \times \log m)$，暴力为 $O(n \times m)$，二分把外层从线性降为对数；
• 三个工程要点必须落实：向上取整计时、边界[1, max(piles)]、耗时累加用 64 位整数；
• articles/eating-bananas.md 提供了九种语言的完整对照代码，仓库中 12 份语言实现（如 python/0875-koko-eating-bananas.py、java/0875-koko-eating-bananas.java）则展示了左边界二分的多种等价写法，可结合阅读。

掌握“二分答案”这一模式后，遇到“给定约束求最小化/最大化某个参数”的题型（如装运包裹、按天分配容量等），都可以按“界定答案区间 → 写单调判定函数 → 二分找分界”三步套用。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode