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的速度即为答案。算法步骤令speed 1对每个速度计算所有堆的ceil(pile / speed)之和若总和 h返回当前速度否则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 speedC 版本展示了不依赖浮点的向上取整写法class Solution { public: int minEatingSpeed(vectorint 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)是常见错误区间虽然仍然正确但比必要的更大白白增加二分迭代次数。算法步骤设搜索区间left 1right max(piles)并初始化res right当left right取mid (left right) // 2作为待测速度计算总耗时若总耗时 h该速度可行记录res mid搜左半区right mid - 1否则速度太慢搜右半区left mid 1循环结束后返回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 份语言实现它们与文档的算法骨架一致但在工程细节上各有取舍值得逐一比对文件二分形态值得注意的细节python/0875-koko-eating-bananas.pywhile l r找左边界与文档最优解完全一致res r初始化保证有返回值java/0875-koko-eating-bananas.javawhile (left right)无res变量用right middle/left middle 1收缩最终return right先线性扫一遍求right max(piles)cpp/0875-koko-eating-bananas.cppwhile (low high)并维护result文件头注释写明O(n x log m) / O(1)并用long int hours防溢出javascript/0875-koko-eating-bananas.js开区间左边界mid (left right) 1抽出getHourSpent纯函数计算耗时便于单测go/0875-koko-eating-bananas.go上界取10^9题目约束上限canEat在累加过程中提前返回pruning避免无效累加rust/0875-koko-eating-bananas.rswhile l r用((num_bananas - 1) / m) 1实现无浮点向上取整kotlin/0875-koko-eating-bananas.kt、typescript/0875-koko-eating-bananas.ts、swift/0875-koko-eating-bananas.swift、csharp/0875-koko-eating-bananas.cs、ruby/0875-koko-eating-bananas.rb、c/0875-koko-eating-bananas.c—同一题目的其余语言版本可作跨语言写法对照从源码结构看这些实现体现了三种常见的二分写法变体①闭区间 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) // speedC 版 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 totalTimeC 用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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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的速度即为答案。算法步骤令speed 1对每个速度计算所有堆的ceil(pile / speed)之和若总和 h返回当前速度否则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 speedC 版本展示了不依赖浮点的向上取整写法class Solution { public: int minEatingSpeed(vectorint 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)是常见错误区间虽然仍然正确但比必要的更大白白增加二分迭代次数。算法步骤设搜索区间left 1right max(piles)并初始化res right当left right取mid (left right) // 2作为待测速度计算总耗时若总耗时 h该速度可行记录res mid搜左半区right mid - 1否则速度太慢搜右半区left mid 1循环结束后返回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 份语言实现它们与文档的算法骨架一致但在工程细节上各有取舍值得逐一比对文件二分形态值得注意的细节python/0875-koko-eating-bananas.pywhile l r找左边界与文档最优解完全一致res r初始化保证有返回值java/0875-koko-eating-bananas.javawhile (left right)无res变量用right middle/left middle 1收缩最终return right先线性扫一遍求right max(piles)cpp/0875-koko-eating-bananas.cppwhile (low high)并维护result文件头注释写明O(n x log m) / O(1)并用long int hours防溢出javascript/0875-koko-eating-bananas.js开区间左边界mid (left right) 1抽出getHourSpent纯函数计算耗时便于单测go/0875-koko-eating-bananas.go上界取10^9题目约束上限canEat在累加过程中提前返回pruning避免无效累加rust/0875-koko-eating-bananas.rswhile l r用((num_bananas - 1) / m) 1实现无浮点向上取整kotlin/0875-koko-eating-bananas.kt、typescript/0875-koko-eating-bananas.ts、swift/0875-koko-eating-bananas.swift、csharp/0875-koko-eating-bananas.cs、ruby/0875-koko-eating-bananas.rb、c/0875-koko-eating-bananas.c—同一题目的其余语言版本可作跨语言写法对照从源码结构看这些实现体现了三种常见的二分写法变体①闭区间 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) // speedC 版 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 totalTimeC 用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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考