1. 题目解读与破题思路1.1 题目到底在问什么LeetCode Hot 100 我已经刷到第 9 题了今天这道题是 875 题“爱吃香蕉的狒狒”编号 9_100在 Hot 100 里属于二分查找这个标签下的经典题。题目本身是一个卷故事背景的应用题但剥开壳子之后它实际上是一道非常标准的“二分答案”问题。先把题意说清楚。一堆香蕉分成 N 堆第 i 堆有 piles[i] 根香蕉现在有只狒狒要在 h 小时内把这些香蕉全部吃完。狒狒的进食规则有两个硬性限制一是每小时最多只能选择一堆香蕉不能同时吃两堆二是如果这一堆香蕉的根数大于狒狒当前的速度 k也就是每小时能吃 k 根那它在这一堆上要花多个小时才能吃完并且吃不完的只能留到下一个小时继续吃同一堆不能中途换堆。要求我们求一个最小的整数速度 k使得狒狒能够在 h 小时内把所有的香蕉全部吃完。很多同学第一次看到这道题会觉得像模拟题想着能不能从小到大枚举速度 k然后模拟吃的过程。思路本身没错但你先看一眼数据范围piles 数组长度最多到 10^4每堆香蕉数量最多到 10^9h 最大到 10^9。如果从 1 枚举到 10^9再嵌套遍历一遍 piles最坏情况是 10^9 乘以 10^4 的计算量显然会超时。所以我们不能暴力枚举答案而要想办法更聪明地找到这个 k。1.2 为什么一眼看出要用二分判断一道题能不能用二分关键看问题的答案是否具有单调性。这道题里如果狒狒以某个速度 k 能在 h 小时内吃完所有香蕉那么用比 k 更大的速度 k1 去吃花的时间只会更短那么也一定能在 h 小时内吃完。反过来如果速度 k 来不及吃完那所有比 k 小的速度也一定来不及。这就是典型的单调性质。把这个问题换一种说法给定一个速度 k我们可以快速算出一个总耗时 f(k)那么 f(k) 随着 k 的增大严格递减。我们要找的答案就是满足 f(k) h 的最小 k也就是在单调递减函数上做二分查找。这种“求满足某个条件的最优数值”的问题在算法竞赛里有个术语叫“二分答案”。它的核心不是把二分用在数组下标上而是把二分用在可能的答案范围上。我们要做的不是在一堆元素里找一个值而是在一个连续的取值区间里找到一个满足条件的边界值。这类题型的典型标志就是答案是一个具体的数值而且这个数值有一个可判定的条件函数。Koko 这道题非常典型因为它的条件函数 f(k) 特别好写。思路确立之后整个问题就变成了确定上下界选一个中点 k判定 k 是否可行然后不断缩小区间。整个过程复杂度是 O(N log M)N 是堆数M 是最大堆的香蕉数量算下来完全不慌。2. 核心算法拆解2.1 二分上下界怎么定很多新手在二分题上栽跟头不是因为二分模板不熟而是因为上下界搞不清楚。先说下界。狒狒每小时至少要吃掉一根香蕉不然它就得在香蕉旁边待到天荒地老。所以下界可以设为 1。再看上界。假设狒狒每小时能吃 max(piles) 根香蕉也就是一次性能把最大的一堆吃完。那这种情况下它对每一堆都只需要一小时就能解决总体上耗时 n 小时n 是堆数。如果速度比 max(piles) 还大比如 max(piles) 1每堆仍然需要一小时总耗时还是 n 小时并不会更快。所以超过 max(piles) 的速度没有实际意义上界取 max(piles) 就足够了。这里要特别解释一个容易误解的点为什么上界不能是 N 或者 h因为这个题的速度指的是“每小时吃多少根香蕉”不是“每小时能吃多少堆”。速度的最大值应该由单堆的最大值决定跟堆数 N 没有直接关系。你想想一堆香蕉有 10^9 根那你一小时最多能吃掉 10^9 根吗理论上可以如果这堆香蕉数目是 10^9那一小时正好吃完这个就是速度上限。再多没有意义因为每小时最多只能吃一堆多吃的部分根本没地方用。确认了上下界之后二分区间就是 [1, max(piles)]。这个区间很大比如最大堆是 10^9那么二分大概需要 log2(10^9) 次约 30 次左右每一次遍历 piles 数组是 10^4 次操作总共才 30 万次运算对计算机而言连零头都算不上。这也是二分答案的魅力所在把指数级的枚举变成了对数级的搜索。2.2 判定函数的写法与吃时间的计算有了上下界接下来要写就是整个题目最关键的函数——判定函数。给定一个速度 k我们需要算出吃完所有香蕉需要的总小时数然后和 h 比较。这里最核心的是一个取整公式。对于一堆有 pile 根香蕉的堆狒狒以速度 k 去吃吃完这一堆需要多少小时如果 pile 正好能被 k 整除那答案是 pile / k如果不能整除就需要向上取整也就是 (pile k - 1) / k。为什么是 (pile k - 1) / k 这个写法因为它巧妙地实现了整数除法向上取整。我们来拆开看假设 pile 10k 3正常除法 10 / 3 3但实际上狒狒需要 4 小时才能吃完 10 根前三个小时每小时吃 3 根最后一小时吃剩下 1 根。所以需要向上取整。而 (10 3 - 1) / 3 12 / 3 4正好得到正确结果。这个公式非常常用在算法题里可以当成一个固定技巧记下来。但是要注意的是写完这个公式之后别高兴得太早还有个隐藏很深的坑整数溢出。当 pile 和 k 都很大时pile k - 1 可能会超出 int 的范围。比如 pile 10^9k 我们也取到 10^9 量级pile k 就接近 2 × 10^9虽然还在 32 位 int 范围内int 上限约 2.147 × 10^9但如果数据再变态一点就顶不住了。而且更常见的是在凑整公式上做加法时可能会越界。所以稳妥的做法是把相关变量声明成 long long或者用另一种等价写法(pile - 1) / k 1也能实现向上取整同时把加法溢出风险降到最低。我在实际刷题时更喜欢用 (pile - 1) / k 1 这个写法因为它的语义更接近“先少看一根看看能分成几段满的然后再补一段”。两个公式结果完全一样但后者在某些极端数据下更安全。代码里我会预留 long long 的转型宁可多写两行也不能让溢出这种低级错误毁了整道题。3. 实操过程与代码实现3.1 C 实现与代码注释二分模板我倾向于用“左闭右开”的写法也就是区间 [left, right)这样在更新边界时不会出现死循环的问题。上界我取 max(piles)然后 right maxPile 1表示右边界本身是一个不可行值这样天然满足左闭右开区间的定义。完整代码长这样class Solution { public: int minEatingSpeed(vectorint piles, int h) { int maxPile 0; for (int pile : piles) { maxPile max(maxPile, pile); } int left 1; int right maxPile 1; while (left right) { int mid left (right - left) / 2; if (canFinish(piles, h, mid)) { right mid; } else { left mid 1; } } return left; } private: bool canFinish(vectorint piles, int h, int speed) { long long time 0; for (int pile : piles) { time (pile - 1) / speed 1; if (time h) { return false; } } return time h; } };我来逐段解释一下这个代码里每个关键细节。canFinish 函数里的提前返回非常关键。有些同学会把所有堆的时间全部累加完再去和 h 比较这在数据量小的时候没问题但在某些测试用例下会白白浪费计算。如果 time 累加的过程中已经超过了 h那就可以立即返回 false因为后面的堆就算不吃也已经超时了。这个剪枝在极端情况下能省不少时间属于编码习惯问题。另一个细节是 mid left (right - left) / 2而不是 (left right) / 2。虽然两者在数学上等价但前者能避免 left right 溢出。在二分答案问题里left 和 right 都可能达到 10^9 级别相加后可能超过 int 最大值用这个写法更安全。这个习惯我在所有二分题目里都保持哪怕明知道不会溢出也会这么写形成肌肉记忆后不容易在边界数据上翻车。3.2 左闭右闭与左闭右开两种模板的差异很多同学会纠结二分模板到底用哪种好。这个问题我专门聊一下因为我见过太多人在模板上出了问题调试半天发现是边界写错了。左闭右闭也就是用 while (left right)更新时 left mid 1 或 right mid - 1。这种方式在退出循环后left 就是第一个满足条件的位置但需要特别小心 mid 的更新和最终返回值。左闭右开用 while (left right)更新时 left mid 1 或 right mid。这种方式的好处是语义更统一left 始终指向一个可行区域的左边界right 指向不可行区域或者越界位置循环结束时 left 和 right 重合这个位置就是我们要找的答案。我个人的经验是二分答案类问题用左闭右开更顺手。原因是当我们需要查找“最小可行值”时左闭右开天然维护了一个区间左边界是可行区右边界是不可行区每次二分都在缩小这个区间范围。判断条件和边界更新也变得更直观mid 可行就收缩右边界把不可行区拉低mid 不可行就把左边界抬高。最终重合的位置就是答案。但这不代表左闭右闭不能用。两种模板都能 AC关键是你要完全搞清楚自己在写的是哪一种然后对应上正确的更新逻辑。最忌讳的是左闭右闭的 while 条件配上了左闭右开的更新逻辑这样写出来的代码基本必死循环或者漏边界。我在实战里就把两种模板分别写在了笔记里每次做题前先在心里确认一遍模板再动手敲代码。4. 常见问题与排查技巧实录4.1 判定函数的取整坑这道题最常见的错误不是二分写错而是判定函数的取整写错。我见过最多的错误版本是 time pile / speed。这个写法在 pile 能被 speed 整除时没错比如 10 个香蕉每小时吃 5 个结果是 2 小时没问题。但一旦不能整除比如 10 个香蕉每小时吃 3 个pile / speed 10 / 3 3而实际需要 4 小时。这直接导致判定函数低估了总耗时原本应该不可行的速度被判成可行最后得到的答案就会偏小。调试这种题时有个非常有效的办法把 canFinish 函数单独拎出来手动输入一些极端的小数据来验证。比如 piles [3, 6, 7, 11]h 8速度 k 4 时每堆耗时分别是 1、2、2、3总耗时 8正好满足条件。k 3 时每堆耗时 1、2、3、4总耗时 10超时。如果代码里用了错误的取整那么在 k 3 时很可能会算出 1 2 2 3 8导致误判成可行。这种边界 case 一旦出现二分的结果就会差出一个数量级。所以我的建议是写完判定函数后先不要急着提交手动构造两组数据算一遍一组覆盖整除情况一组覆盖不整除情况把取整逻辑验证清楚再提交。这种习惯能帮你省下大量无谓的提交和调试时间。4.2 二分死循环与边界更新另一个高频问题就是二分死循环。死循环的根源在于 mid 的计算和 left/right 的更新方式不匹配。常见的死循环场景是当 left 3right 4 时mid 3 (4 - 3) / 2 3如果此时 canFinish(3) 返回 true代码执行 right mid 3区间变为 [3, 3)循环退出没问题。但如果 canFinish(3) 返回 false代码执行 left mid 1 4区间变为 [4, 4)循环退出也没问题。那什么情况下会死循环呢如果你把 mid 的取整方式改成 mid (left right 1) / 2也就是向上取整那么当 left 3right 4 时mid 4。如果 canFinish(4) 返回 true执行 right mid 4区间仍然是 [3, 4)mid 下一次还是 4于是永远无法收敛。这就是典型的“向上取整 right mid”组合导致的死循环。解决死循环的办法有两个方向要么用向下取整的 mid 配合 left mid 1、right mid 的更新方式也就是我上面代码里的写法要么用向上取整的 mid 配合 left mid、right mid - 1 的更新方式。关键是不要混用。模板的匹配关系记牢之后死循环问题基本就绝迹了。如果实在不放心可以在本地写一个测试脚本把 h 设成很极限的值比如 h piles.size()然后看代码是否会正常退出。这道题因为 h 最小是 n所以极限场景正好覆盖了“每小时一堆全吃完”的情况适合用来验证边界逻辑。4.3 数据范围与类型溢出题目给的数据范围你仔细看会发现一些有意思的地方。piles[i] 最大是 10^9h 最大也是 10^9。虽然 h 很大但并不意味着我们可以随意放宽条件。先确认一个数学上的必然如果 h piles.size()那么一定存在一个可行解因为狒狒至少可以每小时吃一大坨每堆一小时正好堆数小时内完成。而题目的约束保证了 h 一定大于等于堆数不然这道题就没有解了。这也是为什么我们不需要考虑无解的情况直接二分就行。但在计算过程中time 变量的类型值得注意。虽然单个堆的耗时不会超过 10^9但如果把所有堆累加起来总耗时可能超过 int 范围。比如 piles 里有 10^4 堆每堆耗时 10^9 小时那总耗时是 10^13 量级这远远超过了 32 位 int 的上限。所以 canFinish 函数里 time 一定要用 long long 类型不然累加到一定程度就会溢出变成负数然后 time h 的判断就会出错整个二分会往错误方向走。还有一个隐藏的溢出点就是 (pile - 1) / speed 1 这个表达式里虽然 (pile - 1) 和 speed 都是 int但 pile - 1 可能在极端情况下等于 10^9 - 1仍在 int 范围内。但如果我用了 (pile speed - 1) / speed 这种写法pile speed - 1 可能达到 2 × 10^9勉强在 int 内不过一旦数据稍微加码就悬了。所以除了 time 用 long long我还会在累加时强制把 speed 转换成 long long确保中间计算不越界。4.4 手写测试用例与边界验证刷题时我习惯在提交之前先跑一组自己的测试用例。这题我常用的几组用例第一组是官方样例 piles [3, 6, 7, 11]h 8预期输出 4。这组数据覆盖了整除和不整除两种情况能很快验证判定函数是否正确。第二组是 piles [30, 11, 23, 4, 20]h 5预期输出 30。这组数据的 h 正好是堆数意味着狒狒必须每小时解决一堆所以答案必须等于最大堆的香蕉数 30。如果二分模板写错这组数据很容易测出来。第三组是 piles [30, 11, 23, 4, 20]h 6预期输出 23。这组数据相对不那么直观但如果你理解了判定函数的逻辑可以手算验证。第四组是边界数据 piles [1000000000]h 1预期输出 1000000000。只有一堆要在一小时内吃完速度必须等于这一堆的根数。这个用例能验证上界的正确性。第五组是 piles [2, 2]h 2预期输出 2。这个用例很刁钻因为如果速度是 1两堆各需要 2 小时总共 4 小时超时速度是 2 时每堆 1 小时总共 2 小时刚好。它能验证答案边界没有被二分遗漏。把这五组数据在提交前跑一跑基本上所有常见的问题都能提前暴露出来。我在实际刷题中验证过用这些用例能覆盖到大部分同学的错法。5. 这类题的通法最大值最小化问题5.1 从 Koko 到二分答案的通用套路Koko 这道题做完之后很多同学会有一种感觉这题我好像悟到了点什么但说不清。我试着帮你把这个“说不清”的东西提炼成可以复用的套路。二分答案题型的典型特征有两个。第一个特征是题目要求我们求一个最优的整数数值比如最小速度、最小容量、最短天数、最大距离。第二个特征是存在一个判定函数给定这个数值我们能快速判断是否满足题目的约束。这两个特征同时满足就可以考虑用二分答案。这套题型的通用框架是四步走。第一步确定二分区间下界通常是某个业务上的最小值比如每小时至少吃 1 根上界通常是某个业务上的最大值比如一次最多吃 1 堆也就是最大堆的数量有时候上界可以直接取一个足够大的数比如 10^14。第二步写出判定函数这个函数接收一个候选值返回能否完成任务。第三步在区间上套二分模板找边界找到满足条件的最值。第四步检查边界和数据范围防止溢出和死循环。用这个框架反观 Koko 这道题答案是速度 k区间是 [1, max(piles)]判定函数是能否在 h 小时内吃完这就是一套标准的二分答案题解。你做过的每一道二分答案题本质上都在套这个模板。5.2 相关题目扩展二分答案的套路一旦掌握能一口气打通不少 LeetCode 上的经典题。这里我列几道和 Koko 高度相关的题目方便你做后续巩固。1011 题“在 D 天内送达包裹的能力”是 Koko 的孪生题。题目要求在 D 天内把包裹按顺序运完求船的最小运载能力。这里的答案区间是 [max(weights), sum(weights)]判定函数是给定运载能力能否在 D 天内运完。代码结构和 Koko 几乎一模一样只是把“吃香蕉的时间”换成了“运包裹的天数”。410 题“分割数组的最大值”稍微进阶一点。题目要求把数组分成 m 个连续子数组使得这些子数组和的最大值最小。这题的答案区间是 [max(nums), sum(nums)]判定函数是给定一个最大和能否把数组分割成不超过 m 段。理解了 Koko 之后再做这道题思路会顺畅很多。还有 1482 题“制作 m 束花所需的最少天数”这道题把二分答案套在了“天数”上判定条件是给定天数能否收集到足够的花。结构上也是同一个套路但判定函数的实现稍微复杂一点需要扫描数组统计连续满足条件的区间。这几道题建议你们在刷完 Koko 之后一周内去刷掉趁热打铁把二分答案这套思路彻底消化掉。5.3 我刷二分答案题的一些心得体会说点务实的。二分答案题刷到一定数量之后你会发现自己对“单调性”这三个字特别敏感。拿到一道题先不急着想怎么模拟、怎么贪心而是先问自己这题的答案是一个数吗这个数的变化会引起结果单调变化吗如果答案是肯定的那多半就是二分答案。但这里有个容易误判的地方单调性不是指“答案越大越好”或者“答案越小越好”而是指“满足条件的答案集合是一个连续区间”。比如 Koko 这题速度 k 从某个临界值往上全都满足条件往下全都不满足。这个集合是连续的、没有断裂的。具备这种性质的题目才能用二分。如果满足条件的答案集合是一堆散点比如 k 2 和 k 5 都行但 k 3 不行那就不能二分只能老老实实枚举或者换思路。在实际工作中二分答案的思想也没少用到。比如在监控系统里调某个超时时间参数或者在做推荐系统时调一个分数阈值本质上都是一种二分调参的思路先给定一个值看效果是否达标然后根据反馈不断调整。虽然题目里用的是程序化二分但思维模式是相通的。这也算是我刷算法题一个意外的收获。最后分享一个小技巧如果你在做 Koko 这题时感觉思路卡住了可以画一个图表横轴是速度 k纵轴是总耗时 f(k)。你会发现 f(k) 是一条单调递减的阶梯曲线。我们要找的答案就是这条曲线第一次掉到 h 以下时的横坐标。这个可视化对理解二分答案非常有帮助一旦脑海里有了这个图像很多边界问题都能迎刃而解。我在给组里新人讲这道题时也经常用这个图基本上画完图他们都懂了比讲一堆边界条件有用得多。
LeetCode 875 爱吃香蕉的狒狒：二分答案法详解与C++实现
1. 题目解读与破题思路1.1 题目到底在问什么LeetCode Hot 100 我已经刷到第 9 题了今天这道题是 875 题“爱吃香蕉的狒狒”编号 9_100在 Hot 100 里属于二分查找这个标签下的经典题。题目本身是一个卷故事背景的应用题但剥开壳子之后它实际上是一道非常标准的“二分答案”问题。先把题意说清楚。一堆香蕉分成 N 堆第 i 堆有 piles[i] 根香蕉现在有只狒狒要在 h 小时内把这些香蕉全部吃完。狒狒的进食规则有两个硬性限制一是每小时最多只能选择一堆香蕉不能同时吃两堆二是如果这一堆香蕉的根数大于狒狒当前的速度 k也就是每小时能吃 k 根那它在这一堆上要花多个小时才能吃完并且吃不完的只能留到下一个小时继续吃同一堆不能中途换堆。要求我们求一个最小的整数速度 k使得狒狒能够在 h 小时内把所有的香蕉全部吃完。很多同学第一次看到这道题会觉得像模拟题想着能不能从小到大枚举速度 k然后模拟吃的过程。思路本身没错但你先看一眼数据范围piles 数组长度最多到 10^4每堆香蕉数量最多到 10^9h 最大到 10^9。如果从 1 枚举到 10^9再嵌套遍历一遍 piles最坏情况是 10^9 乘以 10^4 的计算量显然会超时。所以我们不能暴力枚举答案而要想办法更聪明地找到这个 k。1.2 为什么一眼看出要用二分判断一道题能不能用二分关键看问题的答案是否具有单调性。这道题里如果狒狒以某个速度 k 能在 h 小时内吃完所有香蕉那么用比 k 更大的速度 k1 去吃花的时间只会更短那么也一定能在 h 小时内吃完。反过来如果速度 k 来不及吃完那所有比 k 小的速度也一定来不及。这就是典型的单调性质。把这个问题换一种说法给定一个速度 k我们可以快速算出一个总耗时 f(k)那么 f(k) 随着 k 的增大严格递减。我们要找的答案就是满足 f(k) h 的最小 k也就是在单调递减函数上做二分查找。这种“求满足某个条件的最优数值”的问题在算法竞赛里有个术语叫“二分答案”。它的核心不是把二分用在数组下标上而是把二分用在可能的答案范围上。我们要做的不是在一堆元素里找一个值而是在一个连续的取值区间里找到一个满足条件的边界值。这类题型的典型标志就是答案是一个具体的数值而且这个数值有一个可判定的条件函数。Koko 这道题非常典型因为它的条件函数 f(k) 特别好写。思路确立之后整个问题就变成了确定上下界选一个中点 k判定 k 是否可行然后不断缩小区间。整个过程复杂度是 O(N log M)N 是堆数M 是最大堆的香蕉数量算下来完全不慌。2. 核心算法拆解2.1 二分上下界怎么定很多新手在二分题上栽跟头不是因为二分模板不熟而是因为上下界搞不清楚。先说下界。狒狒每小时至少要吃掉一根香蕉不然它就得在香蕉旁边待到天荒地老。所以下界可以设为 1。再看上界。假设狒狒每小时能吃 max(piles) 根香蕉也就是一次性能把最大的一堆吃完。那这种情况下它对每一堆都只需要一小时就能解决总体上耗时 n 小时n 是堆数。如果速度比 max(piles) 还大比如 max(piles) 1每堆仍然需要一小时总耗时还是 n 小时并不会更快。所以超过 max(piles) 的速度没有实际意义上界取 max(piles) 就足够了。这里要特别解释一个容易误解的点为什么上界不能是 N 或者 h因为这个题的速度指的是“每小时吃多少根香蕉”不是“每小时能吃多少堆”。速度的最大值应该由单堆的最大值决定跟堆数 N 没有直接关系。你想想一堆香蕉有 10^9 根那你一小时最多能吃掉 10^9 根吗理论上可以如果这堆香蕉数目是 10^9那一小时正好吃完这个就是速度上限。再多没有意义因为每小时最多只能吃一堆多吃的部分根本没地方用。确认了上下界之后二分区间就是 [1, max(piles)]。这个区间很大比如最大堆是 10^9那么二分大概需要 log2(10^9) 次约 30 次左右每一次遍历 piles 数组是 10^4 次操作总共才 30 万次运算对计算机而言连零头都算不上。这也是二分答案的魅力所在把指数级的枚举变成了对数级的搜索。2.2 判定函数的写法与吃时间的计算有了上下界接下来要写就是整个题目最关键的函数——判定函数。给定一个速度 k我们需要算出吃完所有香蕉需要的总小时数然后和 h 比较。这里最核心的是一个取整公式。对于一堆有 pile 根香蕉的堆狒狒以速度 k 去吃吃完这一堆需要多少小时如果 pile 正好能被 k 整除那答案是 pile / k如果不能整除就需要向上取整也就是 (pile k - 1) / k。为什么是 (pile k - 1) / k 这个写法因为它巧妙地实现了整数除法向上取整。我们来拆开看假设 pile 10k 3正常除法 10 / 3 3但实际上狒狒需要 4 小时才能吃完 10 根前三个小时每小时吃 3 根最后一小时吃剩下 1 根。所以需要向上取整。而 (10 3 - 1) / 3 12 / 3 4正好得到正确结果。这个公式非常常用在算法题里可以当成一个固定技巧记下来。但是要注意的是写完这个公式之后别高兴得太早还有个隐藏很深的坑整数溢出。当 pile 和 k 都很大时pile k - 1 可能会超出 int 的范围。比如 pile 10^9k 我们也取到 10^9 量级pile k 就接近 2 × 10^9虽然还在 32 位 int 范围内int 上限约 2.147 × 10^9但如果数据再变态一点就顶不住了。而且更常见的是在凑整公式上做加法时可能会越界。所以稳妥的做法是把相关变量声明成 long long或者用另一种等价写法(pile - 1) / k 1也能实现向上取整同时把加法溢出风险降到最低。我在实际刷题时更喜欢用 (pile - 1) / k 1 这个写法因为它的语义更接近“先少看一根看看能分成几段满的然后再补一段”。两个公式结果完全一样但后者在某些极端数据下更安全。代码里我会预留 long long 的转型宁可多写两行也不能让溢出这种低级错误毁了整道题。3. 实操过程与代码实现3.1 C 实现与代码注释二分模板我倾向于用“左闭右开”的写法也就是区间 [left, right)这样在更新边界时不会出现死循环的问题。上界我取 max(piles)然后 right maxPile 1表示右边界本身是一个不可行值这样天然满足左闭右开区间的定义。完整代码长这样class Solution { public: int minEatingSpeed(vectorint piles, int h) { int maxPile 0; for (int pile : piles) { maxPile max(maxPile, pile); } int left 1; int right maxPile 1; while (left right) { int mid left (right - left) / 2; if (canFinish(piles, h, mid)) { right mid; } else { left mid 1; } } return left; } private: bool canFinish(vectorint piles, int h, int speed) { long long time 0; for (int pile : piles) { time (pile - 1) / speed 1; if (time h) { return false; } } return time h; } };我来逐段解释一下这个代码里每个关键细节。canFinish 函数里的提前返回非常关键。有些同学会把所有堆的时间全部累加完再去和 h 比较这在数据量小的时候没问题但在某些测试用例下会白白浪费计算。如果 time 累加的过程中已经超过了 h那就可以立即返回 false因为后面的堆就算不吃也已经超时了。这个剪枝在极端情况下能省不少时间属于编码习惯问题。另一个细节是 mid left (right - left) / 2而不是 (left right) / 2。虽然两者在数学上等价但前者能避免 left right 溢出。在二分答案问题里left 和 right 都可能达到 10^9 级别相加后可能超过 int 最大值用这个写法更安全。这个习惯我在所有二分题目里都保持哪怕明知道不会溢出也会这么写形成肌肉记忆后不容易在边界数据上翻车。3.2 左闭右闭与左闭右开两种模板的差异很多同学会纠结二分模板到底用哪种好。这个问题我专门聊一下因为我见过太多人在模板上出了问题调试半天发现是边界写错了。左闭右闭也就是用 while (left right)更新时 left mid 1 或 right mid - 1。这种方式在退出循环后left 就是第一个满足条件的位置但需要特别小心 mid 的更新和最终返回值。左闭右开用 while (left right)更新时 left mid 1 或 right mid。这种方式的好处是语义更统一left 始终指向一个可行区域的左边界right 指向不可行区域或者越界位置循环结束时 left 和 right 重合这个位置就是我们要找的答案。我个人的经验是二分答案类问题用左闭右开更顺手。原因是当我们需要查找“最小可行值”时左闭右开天然维护了一个区间左边界是可行区右边界是不可行区每次二分都在缩小这个区间范围。判断条件和边界更新也变得更直观mid 可行就收缩右边界把不可行区拉低mid 不可行就把左边界抬高。最终重合的位置就是答案。但这不代表左闭右闭不能用。两种模板都能 AC关键是你要完全搞清楚自己在写的是哪一种然后对应上正确的更新逻辑。最忌讳的是左闭右闭的 while 条件配上了左闭右开的更新逻辑这样写出来的代码基本必死循环或者漏边界。我在实战里就把两种模板分别写在了笔记里每次做题前先在心里确认一遍模板再动手敲代码。4. 常见问题与排查技巧实录4.1 判定函数的取整坑这道题最常见的错误不是二分写错而是判定函数的取整写错。我见过最多的错误版本是 time pile / speed。这个写法在 pile 能被 speed 整除时没错比如 10 个香蕉每小时吃 5 个结果是 2 小时没问题。但一旦不能整除比如 10 个香蕉每小时吃 3 个pile / speed 10 / 3 3而实际需要 4 小时。这直接导致判定函数低估了总耗时原本应该不可行的速度被判成可行最后得到的答案就会偏小。调试这种题时有个非常有效的办法把 canFinish 函数单独拎出来手动输入一些极端的小数据来验证。比如 piles [3, 6, 7, 11]h 8速度 k 4 时每堆耗时分别是 1、2、2、3总耗时 8正好满足条件。k 3 时每堆耗时 1、2、3、4总耗时 10超时。如果代码里用了错误的取整那么在 k 3 时很可能会算出 1 2 2 3 8导致误判成可行。这种边界 case 一旦出现二分的结果就会差出一个数量级。所以我的建议是写完判定函数后先不要急着提交手动构造两组数据算一遍一组覆盖整除情况一组覆盖不整除情况把取整逻辑验证清楚再提交。这种习惯能帮你省下大量无谓的提交和调试时间。4.2 二分死循环与边界更新另一个高频问题就是二分死循环。死循环的根源在于 mid 的计算和 left/right 的更新方式不匹配。常见的死循环场景是当 left 3right 4 时mid 3 (4 - 3) / 2 3如果此时 canFinish(3) 返回 true代码执行 right mid 3区间变为 [3, 3)循环退出没问题。但如果 canFinish(3) 返回 false代码执行 left mid 1 4区间变为 [4, 4)循环退出也没问题。那什么情况下会死循环呢如果你把 mid 的取整方式改成 mid (left right 1) / 2也就是向上取整那么当 left 3right 4 时mid 4。如果 canFinish(4) 返回 true执行 right mid 4区间仍然是 [3, 4)mid 下一次还是 4于是永远无法收敛。这就是典型的“向上取整 right mid”组合导致的死循环。解决死循环的办法有两个方向要么用向下取整的 mid 配合 left mid 1、right mid 的更新方式也就是我上面代码里的写法要么用向上取整的 mid 配合 left mid、right mid - 1 的更新方式。关键是不要混用。模板的匹配关系记牢之后死循环问题基本就绝迹了。如果实在不放心可以在本地写一个测试脚本把 h 设成很极限的值比如 h piles.size()然后看代码是否会正常退出。这道题因为 h 最小是 n所以极限场景正好覆盖了“每小时一堆全吃完”的情况适合用来验证边界逻辑。4.3 数据范围与类型溢出题目给的数据范围你仔细看会发现一些有意思的地方。piles[i] 最大是 10^9h 最大也是 10^9。虽然 h 很大但并不意味着我们可以随意放宽条件。先确认一个数学上的必然如果 h piles.size()那么一定存在一个可行解因为狒狒至少可以每小时吃一大坨每堆一小时正好堆数小时内完成。而题目的约束保证了 h 一定大于等于堆数不然这道题就没有解了。这也是为什么我们不需要考虑无解的情况直接二分就行。但在计算过程中time 变量的类型值得注意。虽然单个堆的耗时不会超过 10^9但如果把所有堆累加起来总耗时可能超过 int 范围。比如 piles 里有 10^4 堆每堆耗时 10^9 小时那总耗时是 10^13 量级这远远超过了 32 位 int 的上限。所以 canFinish 函数里 time 一定要用 long long 类型不然累加到一定程度就会溢出变成负数然后 time h 的判断就会出错整个二分会往错误方向走。还有一个隐藏的溢出点就是 (pile - 1) / speed 1 这个表达式里虽然 (pile - 1) 和 speed 都是 int但 pile - 1 可能在极端情况下等于 10^9 - 1仍在 int 范围内。但如果我用了 (pile speed - 1) / speed 这种写法pile speed - 1 可能达到 2 × 10^9勉强在 int 内不过一旦数据稍微加码就悬了。所以除了 time 用 long long我还会在累加时强制把 speed 转换成 long long确保中间计算不越界。4.4 手写测试用例与边界验证刷题时我习惯在提交之前先跑一组自己的测试用例。这题我常用的几组用例第一组是官方样例 piles [3, 6, 7, 11]h 8预期输出 4。这组数据覆盖了整除和不整除两种情况能很快验证判定函数是否正确。第二组是 piles [30, 11, 23, 4, 20]h 5预期输出 30。这组数据的 h 正好是堆数意味着狒狒必须每小时解决一堆所以答案必须等于最大堆的香蕉数 30。如果二分模板写错这组数据很容易测出来。第三组是 piles [30, 11, 23, 4, 20]h 6预期输出 23。这组数据相对不那么直观但如果你理解了判定函数的逻辑可以手算验证。第四组是边界数据 piles [1000000000]h 1预期输出 1000000000。只有一堆要在一小时内吃完速度必须等于这一堆的根数。这个用例能验证上界的正确性。第五组是 piles [2, 2]h 2预期输出 2。这个用例很刁钻因为如果速度是 1两堆各需要 2 小时总共 4 小时超时速度是 2 时每堆 1 小时总共 2 小时刚好。它能验证答案边界没有被二分遗漏。把这五组数据在提交前跑一跑基本上所有常见的问题都能提前暴露出来。我在实际刷题中验证过用这些用例能覆盖到大部分同学的错法。5. 这类题的通法最大值最小化问题5.1 从 Koko 到二分答案的通用套路Koko 这道题做完之后很多同学会有一种感觉这题我好像悟到了点什么但说不清。我试着帮你把这个“说不清”的东西提炼成可以复用的套路。二分答案题型的典型特征有两个。第一个特征是题目要求我们求一个最优的整数数值比如最小速度、最小容量、最短天数、最大距离。第二个特征是存在一个判定函数给定这个数值我们能快速判断是否满足题目的约束。这两个特征同时满足就可以考虑用二分答案。这套题型的通用框架是四步走。第一步确定二分区间下界通常是某个业务上的最小值比如每小时至少吃 1 根上界通常是某个业务上的最大值比如一次最多吃 1 堆也就是最大堆的数量有时候上界可以直接取一个足够大的数比如 10^14。第二步写出判定函数这个函数接收一个候选值返回能否完成任务。第三步在区间上套二分模板找边界找到满足条件的最值。第四步检查边界和数据范围防止溢出和死循环。用这个框架反观 Koko 这道题答案是速度 k区间是 [1, max(piles)]判定函数是能否在 h 小时内吃完这就是一套标准的二分答案题解。你做过的每一道二分答案题本质上都在套这个模板。5.2 相关题目扩展二分答案的套路一旦掌握能一口气打通不少 LeetCode 上的经典题。这里我列几道和 Koko 高度相关的题目方便你做后续巩固。1011 题“在 D 天内送达包裹的能力”是 Koko 的孪生题。题目要求在 D 天内把包裹按顺序运完求船的最小运载能力。这里的答案区间是 [max(weights), sum(weights)]判定函数是给定运载能力能否在 D 天内运完。代码结构和 Koko 几乎一模一样只是把“吃香蕉的时间”换成了“运包裹的天数”。410 题“分割数组的最大值”稍微进阶一点。题目要求把数组分成 m 个连续子数组使得这些子数组和的最大值最小。这题的答案区间是 [max(nums), sum(nums)]判定函数是给定一个最大和能否把数组分割成不超过 m 段。理解了 Koko 之后再做这道题思路会顺畅很多。还有 1482 题“制作 m 束花所需的最少天数”这道题把二分答案套在了“天数”上判定条件是给定天数能否收集到足够的花。结构上也是同一个套路但判定函数的实现稍微复杂一点需要扫描数组统计连续满足条件的区间。这几道题建议你们在刷完 Koko 之后一周内去刷掉趁热打铁把二分答案这套思路彻底消化掉。5.3 我刷二分答案题的一些心得体会说点务实的。二分答案题刷到一定数量之后你会发现自己对“单调性”这三个字特别敏感。拿到一道题先不急着想怎么模拟、怎么贪心而是先问自己这题的答案是一个数吗这个数的变化会引起结果单调变化吗如果答案是肯定的那多半就是二分答案。但这里有个容易误判的地方单调性不是指“答案越大越好”或者“答案越小越好”而是指“满足条件的答案集合是一个连续区间”。比如 Koko 这题速度 k 从某个临界值往上全都满足条件往下全都不满足。这个集合是连续的、没有断裂的。具备这种性质的题目才能用二分。如果满足条件的答案集合是一堆散点比如 k 2 和 k 5 都行但 k 3 不行那就不能二分只能老老实实枚举或者换思路。在实际工作中二分答案的思想也没少用到。比如在监控系统里调某个超时时间参数或者在做推荐系统时调一个分数阈值本质上都是一种二分调参的思路先给定一个值看效果是否达标然后根据反馈不断调整。虽然题目里用的是程序化二分但思维模式是相通的。这也算是我刷算法题一个意外的收获。最后分享一个小技巧如果你在做 Koko 这题时感觉思路卡住了可以画一个图表横轴是速度 k纵轴是总耗时 f(k)。你会发现 f(k) 是一条单调递减的阶梯曲线。我们要找的答案就是这条曲线第一次掉到 h 以下时的横坐标。这个可视化对理解二分答案非常有帮助一旦脑海里有了这个图像很多边界问题都能迎刃而解。我在给组里新人讲这道题时也经常用这个图基本上画完图他们都懂了比讲一堆边界条件有用得多。
