开始认真刷LeetCode这件事我拖了很久。倒不是觉得算法不重要而是每次打开题库看到三位数的题目编号和一堆“通过率惨淡”的中等题总有种无从下手的压迫感。直到上个月我给自己定了个规矩不求一天十题只求每天一道凑满100道就写一篇阶段性笔记。于是就有了“Leetcode(1/100)”这个系列的第一篇而这篇我打算好好聊聊“073爱吃香蕉的狒狒”这道题。如果你正在刷LeetCode热门100题或者刚开始用二分查找练手这道题几乎是绕不过去的经典。它表面是个“猴子吃香蕉”的小故事实际上考的是二分答案这个核心算法模型的落地能力。我见过不少人在做这道题时栽在边界条件上也有人根本想不到要用二分。这篇文章我会把自己的解题思路、代码实现、运行时踩过的坑以及怎么把它推广到同类问题上一分不差地摊开讲希望对正在刷题的你有点帮助。1. 为什么“1/100”从二分查找开始1.1 刷题清单怎么选热门100题到底该怎么用先交代一下背景。我在规划这100题的时候并没有老老实实按题号顺序往下刷而是按专题拆着来。LeetCode热门100题是一份非常经典的清单里面覆盖了数组、链表、树、动态规划、贪心、二分查找这些常考考点适合用来做系统训练。但很多人拿到清单后有个误区就是把它当成“顺序表”从第1题一路做到第100题。你这么做的结果是链表题做完三题突然跳到动态规划思维还没切换过来又回到哈希表效率非常低。我的做法是先把清单里的题目按知识点归类再按“简单到中等”的坡度逐类击破。比如数组类先做两数之和、三数之和再做盛最多水的容器链表类先做反转链表再做环形链表二分查找类则从“爱吃香蕉的狒狒”这种典型模型入手再慢慢延伸到“在D天内送达包裹的能力”这类稍微复杂的变体。爬下这篇你可能会问为什么第一篇不是两数之和这种“Hello World”级题目而是选了073这道中等题因为我很清楚自己想突破的不是“会不会写循环”而是“能不能一眼识别出二分答案的模型”。两数之和考的是哈希表的空间换时间而吃香蕉这道题能真正帮你建立“对答案进行二分”的思维习惯。这个思维一旦打通后面很多所谓的难题其实都是换皮。1.2 这道题的整体思路与选型逻辑先看一下题目本身。Koko是一只狒狒面前有N堆香蕉每一堆有piles[i]根香蕉。它每小时可以选一堆吃掉K根香蕉如果这一堆不够K根它就把这堆吃完但这一小时内不会再吃另一堆。现在要求在H小时内吃完所有香蕉问最小速度K是多少。这个描述看起来像个模拟题很多人的第一反应是那我从K1开始试每小时模拟一遍看总时间是不是小于等于H不行就K1再试。理论上这么干肯定能出答案但LeetCode的测试数据里piles的长度最大能到10^4每堆香蕉数量最大能到10^9H可以到10^9量级。暴力枚举K从1到max(piles)意味着可能枚举上亿次每次还要遍历一遍所有堆直接超时。那为什么能用二分因为这里有一个非常关键的单调性吃香蕉的速度越快花的时间一定越短。K1时耗时最长Kmax(piles)时耗时最短。我们要求的是“满足耗时≤H”的最小的K这正好落在“单调函数上找边界”的模型里。所以在1到max(piles)这个区间内对速度做二分搜索每次用“当前速度下到底要花几个小时”这个判定函数来缩小范围最终就能以O(N log M)的复杂度收敛到答案。M是香蕉堆里的最大值N是堆数这个复杂度在本题的约束下完全可以跑满。这套思路就是“二分答案”的经典套路先确定答案的可行区间再写一个检查函数最后在区间里二分缩圈。2. 核心细节解析073这道题到底在考什么2.1 题目约束与边界条件我见过很多人在讨论区问为什么二分的右边界直接取max(piles)而不是取一个更大的数这其实是一开始理解这道题的关键。速度K的含义是“每小时最多吃掉多少根香蕉”如果K已经大于等于最大那一堆的数量那不管面对哪一堆都能在一小时内吃完这一堆。所以即使你把K继续增大到100万总耗时也不可能降得更低。我们验证一下假设最大堆有m根当Km时任意一堆piles[i]需要的用时是ceil(piles[i] / m)因为所有堆都不超过m所以每一堆的耗时都是1总耗时恰好等于堆的数量N。再往上提高K堆数不变总耗时仍然是N。也就是说Km之后的区域已经没办法让总耗时更小答案的最优值必然落在1到m之间。这里还有一个所有新手都容易忽略的边界K的下界必须是1而不是0。速度是0意味着狒狒根本不工作这道题在数学上永远吃不完所以左边界的语义必须从可能的最小值1开始。如果你把left写成0那么二分执行到某个阶段时可能会让mid0一旦进入canEat(0)的判断就会出现除零错误这是很典型的隐蔽bug。还有一点需要注意H的约束。题目保证n H其中n是香蕉堆数。这个条件的意思是即使K取无穷大每小时只吃一堆也要H小时才能吃完所以如果Hn的测试用例出现说明输入本身就无解。只不过题目约束已经排除了这种数据我们不需要在代码里额外判断但如果你把这个函数封装出来给其他场景用最好加一层防御校验。2.2 判定函数canEat的写法决定你能不能过二分的主体框架其实都差不多但真正区分一个人有没有吃透这道题的是canEat这个检查函数怎么写。这里的计算逻辑是遍历每一堆计算在当前速度K下这一堆需要多少小时才能被吃完然后累加判断总耗时是否小于等于H。单堆耗时的公式是ceil(piles[i] / K)这个向上取整很容易写错。我用过两种写法第一种是整数运算技巧(piles[i] K - 1) / K也就是分子加上K-1再整除K。第二种是浮点运算配合ceil但我不推荐因为piles[i]和K都可能到10^9浮点数在极大值下会出现精度误差可能让你二分的结果差1这1的差距在LeetCode上就是Wrong Answer。我自己的习惯是全程整数运算不用浮点数这样既快又稳。整个判定函数的时间复杂度是O(N)N是堆数二分过程中这个函数会被调用大约log(max(piles))次大概30多次整体计算量很小。2.3 二分模板选择左右闭区间怎么处理二分查找的模板在竞赛圈里各派各法有左闭右开也有左闭右闭。我在做这道题时用的是左闭右闭的写法也就是区间[left, right]始终包含潜在的答案。初始化时left1rightmax(piles)每次计算mid调用canEat(mid)判断当前速度是否可行。如果是可行的说明mid速度下能按时吃完那么答案可能是mid也可能是更小的速度所以需要把right调整到mid来缩小范围继续向左逼近。注意这里不要写成rightmid-1因为你还不确定mid-1是否可行直接减1可能会漏掉正确答案。反过来如果不可行说明mid速度太慢了那么答案一定大于mid此时需要把left更新为mid1。这个“可行时右边界不缩1不可行时左边界缩1”的策略很关键能保证循环结束时left就是最小可行速度。有些教程喜欢用while (left right)配一个mid不调整的版本但如果你刚开始刷题我建议先把“闭区间边界手动调整”这套玩明白再去尝试其他流派。因为这一套的每一步都有清晰语义调试起来也直观。3. 实操过程完整代码实现与运行验证3.1 Python版本实现从暴力到二分先给一个最直观的暴力版本方便你体会为什么必须优化。暴力思路是枚举速度K从1到max(piles)对每个K算一遍总耗时找到第一个满足条件的K就返回。from typing import List import math def minEatingSpeed_brutal(piles: List[int], h: int) - int: for k in range(1, max(piles) 1): total_hours 0 for pile in piles: total_hours math.ceil(pile / k) if total_hours h: return k return -1这段代码逻辑完全正确但如果你把它丢进LeetCode面对大规模数据会直接TLE。原因就在于外层循环的范围可能到10^9哪怕每次遍历的开销很小乘在一起也扛不住。再来看看二分优化后的完整版本这也是我最终提交的代码from typing import List def can_eat_all(piles: List[int], speed: int, h: int) - bool: hours 0 for pile in piles: hours (pile speed - 1) // speed if hours h: return False return hours h def minEatingSpeed(piles: List[int], h: int) - int: left, right 1, max(piles) while left right: mid (left right) // 2 if can_eat_all(piles, mid, h): right mid else: left mid 1 return left我在can_eat_all里做了一个小优化累加hours的时候提前判断如果已经超过了h就直接返回False不再计算剩下的堆。这在面对极端大数的时候能省不少时间虽然理论上二分的时间复杂度没变但常数更小实测跑起来也更快。3.2 C版本实现注意整型溢出如果你用C刷题需要注意一个细节piles[i]和speed都是int类型但乘法或加法可能超过int范围。虽然这里用的是除法(pile speed - 1)在极端情况下可能到2*10^9还在int范围内不过一旦遇到更复杂的变体比如速度和时间相乘就非常容易溢出。保险起见我建议把相关变量都声明成long long或者直接用long long做中间计算。class Solution { public: bool canEatAll(vectorint piles, long long speed, int h) { long long hours 0; for (int pile : piles) { hours (pile speed - 1) / speed; if (hours h) return false; } return hours h; } int minEatingSpeed(vectorint piles, int h) { int maxPile 0; for (int pile : piles) { maxPile max(maxPile, pile); } long long left 1, right maxPile; while (left right) { long long mid left (right - left) / 2; if (canEatAll(piles, mid, h)) { right mid; } else { left mid 1; } } return (int)left; } };这里额外提一下C版本里我写了mid left (right - left) / 2而不是(left right) / 2是为了防止leftright本身溢出。虽然这道题数据范围不太可能溢出但这是一个好习惯尤其在处理更大范围的数据时能避免莫名其妙的bug。3.3 测试用例怎么设计才算真的理解了我写完代码后不会直接提交而是先在本地跑几组有代表性的测试用例。简单说我会准备四类数据最小规模回归、全是小堆的场景、只有一堆的超大堆、以及刚好卡在h临界值上的数据。第一类是piles[3, 6, 7, 11], h8这是题目自带的样例答案应该是4。第二类是piles[1, 1, 1], h3这种场景下每一堆都需要单独一小时答案就是1主要用来验证下边界有没有问题。第三类是piles[1000000000], h1只有一堆但数量极大答案应该是1000000000用来验证右边界和大数处理。第四类是piles[2, 2], h4这个答案也是1因为速度1时2小时吃完第一堆再2小时吃完第二堆刚好4小时。把这些用例放到代码里跑一遍如果都能通过再提交LeetCode基本就稳了。很多人在本地不测边界一提交就被极端数据打脸这个习惯建议尽早养成。4. 从一道题看一类题二分答案模型与周赛430体验4.1 把“二分答案”抽象成通用模板吃香蕉这道题做完我最大的收获不是会做这一题而是理解了“二分答案”这个更大的模型。你可以把它当成一个通用模板当题目要求的是“满足某个条件的最小值”或“满足某个条件的最大值”并且这个条件的成立与否随答案变化呈现单调性时就可以在答案的可行域上做二分搜索而不是直接去构造答案。模板一般长这样先确定答案的上下界然后写一个判断函数check(mid)接着在区间里二分逼近最优解。关键在于判断函数能否在可接受的时间内算出来。很多时候check函数的实现比二分本身更难因为它要求你把题目条件完整地转化为一次可计算的过程。我拿吃香蕉这题做个映射答案是速度K区间是[1, max(piles)]check函数是canEatAll判断条件是不超过H小时。如果你能把这个映射关系想清楚那么同样的思路可以直接迁移到另一道经典题“在D天内送达包裹的能力”。那道题只需要把“速度”替换成“每天运货能力”把“堆香蕉”替换成“连续包裹重量”把“H小时”替换成“D天”几乎是一模一样的骨架。4.2 同类题目延展二分查找不止能搜索引很多人对二分的理解局限在“有序数组里找目标值”比如搜索旋转排序数组、查找某个数的位置这类题目搜索的是“数组的索引”。但吃香蕉这道题展示的二分对象完全是另一回事它搜索的是“答案的数值”而这个数值不一定在某个明确的数组里存在它只是在一个连续的整数区间里。这个认知对刷题非常关键因为LeetCode里有一大批中等题都属于这种“对答案做二分”的套路。除了上面提的“在D天内送达包裹的能力”还有“分割数组的最大值”“制作m束花所需的最少天数”“第K个最小的质数分数”等全部可以归入这一类。你一旦掌握了吃香蕉这题的解法再去做这些题时至少能看出“应该用二分答案”至少目标明确了一半。周赛430那阵子我正好在练这类二分答案题顺手复盘了一下当周的题目发现好几题虽然包装复杂底层还是把二分答案和贪心结合。比如有些题给你的输入不是数组而是一个可以实时计算某属性的函数你只能通过调整参数来逼近目标这种时候二分答案几乎是最稳的解法。如果没建立“对答案二分”的意识你很可能一上来就想用模拟或者贪心最后绕进死胡同。4.3 周赛430的启发验证思维比刷题量重要我刷周赛的时候有个很深的感触很多人题刷了不少但遇到新题还是会慌。原因在于刷题时只记题型不记推导过程。吃香蕉这题如果只是背下“用二分”下次遇到“把一堆任务分成若干组求最小最大时间”类的题照样不知道怎么下手。周赛430里的题目让我意识到真正有用的能力是“快速判断一道题能不能二分”。我在脑子里过了这么几个问题答案是不是一个值这个值的范围是不是可以确定随着值变大目标结果是不是单调变化如果三个答案都是“是”那这道题八成就是二分答案。这个思维模型我在吃香蕉这题上反复验证过之后遇到类似题目基本不会再走弯路。另外周赛和日常刷题有个区别周赛有时间压力你必须在半小时内完成读题、建模、编码、调试。所以平时刷题时要刻意训练自己“先写check函数再写二分主逻辑”的节奏。check函数一般是整道题的核心写清楚了二分主体只是套模板而已。5. 常见问题与避坑指南5.1 最容易让人卡住的三个细节我在给身边朋友讲这道题时发现大家卡住的点高度集中。第一个是“向上取整怎么写”这一点我在前面已经强调过用(a b - 1) / b这种整数运算是最稳的。如果你用math.ceil(a / b)在Python里由于除法默认返回浮点数a和b一到大数就可能精度丢失导致结果偏小或者报错。我第一次提交就是因为这个问题翻车后来彻底改成整数运算再也没在这个点上浪费过时间。第二个是“边界为什么是1而不是0”以及“为什么right是max(piles)”这两个问题连在一起容易混。记住速度一定大于等于1而且超过max(piles)后时间不会再减少所以右边界就是max(piles)。这不是一个玄学结论而是可以从总耗时的计算式里推出来的。第三个是“二分的退出条件到底是什么”。我用的是while left right最终left和right相遇时就是答案。如果遇到死循环或者结果偏1的问题大概率是因为更新left和right时没想清楚“mid是否可能是答案”。建议你在更新右边界时用right mid因为mid可能就是最优解不能把它排除更新左边界时用left mid 1因为mid已经确认不可行不用再考虑它。5.2 调试技巧把每一步的mid和耗时打出来如果你在本地测试时发现结果不对最快的排查方式是打印每次二分时的mid值和对应的总耗时。尤其是当返回的答案比预期小1或大1时打日志能立刻看出是边界缩小策略出了问题还是canEatAll的计算逻辑出了问题。我就曾经遇到过一个案例把hours (pile speed - 1) // speed写成了hours pile // speed 1结果当pile刚好能被speed整除时会多算1小时。这种错误在单测里可能完全看不出来只有用特定数据比如piles[2, 2], h4时才会暴露因为我期望答案是1实际却跑出2。打印mid的过程能帮你迅速定位是“判断条件”的问题而不是“二分方向”的问题。还有个小技巧先把暴力解法写出来然后用随机数据对比二分解法和暴力解法。这种对拍方式在竞赛圈很常用放在刷题里也极其好用。只要随机生成一堆测试用例两边输出不一致就说明二分逻辑有bug。这个方法能帮你守住底线不至于在一个隐蔽的错误上纠结半天。5.3 性能与提交如何在LeetCode上稳过这道题的输入规模决定了O(N log M)是完全可以接受的。实际测试里Python版本的运行时间通常在150ms左右C版本更是在20ms以内几乎不会出现性能瓶颈。如果你跑出来特别慢先检查两处一是有没有在循环里重复计算max(piles)二是canEatAll里有没用提前退出的机会。前者是常数优化后者在数据量大的时候能省下不少时间。提交前记得把代码里的日志全部删掉或者在本地调试版本和提交版本之间做一个隔离。LeetCode的判题环境对输出很敏感任何多余打印都会导致Presentation Error或者无谓的时间损耗。我见过不少人在本地测试通过一提交就各种问题最后发现是print语句忘记删了。5.4 常见问题速查表为了方便你保存和回顾我把这道题最常遇到的坑整理成了一张表你可以直接对照排查自己代码里可能出现的问题。问题现象可能原因解决方案除零错误left初始化成了0mid变成0left初始化为1结果比正确答案大1右边界更新为right mid - 1把正确答案排除了改为right mid结果比正确答案小1时间计算里ceil写错了可整除时多算1小时用(pile speed - 1) // speed运行超时暴力枚举K或者canEatAll里没有提前退出改用二分加上hoursh的提前判断浮点数精度出错用了math.ceil(pile / speed)全部改为整数运算返回结果超出int范围C里用int做乘法或加法使用long long做中间计算6. 从073到更多这个系列后面会聊什么这篇作为“Leetcode(1/100)”系列的开篇我特意选了一道中等难度的二分查找题来打底。因为我觉得刷题打卡最重要的不是第一天就冲刺难题而是通过一道题把一个高频考点彻底吃透。接下来这100题里我计划按专题继续整理数组哈希、双指针、滑动窗口、链表、树、回溯、动态规划这几个大方向都会覆盖到。每一篇我都会尽量按照今天这样的格式来写先讲清楚为什么选这道题再拆解思路和边界然后贴完整可运行的代码最后写踩坑记录和同类题扩展。比起单纯贴一个AC代码我更希望能帮你建立一套可复用的思考框架这样哪怕换一道新题你也能举一反三。吃香蕉这道题本身还有个有意思的变体如果狒狒可以提前在某个时刻休息R小时问最小速度是多少或者把“一堆只能一小时一吃”改成“可以同时吃多堆”模型就会从二分答案变成别的算法。这种变体思路挺适合用来检验自己到底有没有真懂原题。我的建议是如果你做完这题还有余力可以先不用看题解自己改改题目条件试着推导一下新解法。回到开头那个问题为什么我的100题计划第一题选它因为我始终相信刷题的意义不在于题量堆积而在于每题都能带走一个能迁移的思维模型。二分答案这个模型值得作为整个系列的起点。下一道题我计划聊聊“两数之和”的哈希表思路当然也可能临时换题毕竟刷题这事还是跟着感觉走更开心。