今天打开LeetCode把昨天磨了一晚上的875题提交页面弹出来“0 msfaster than 100.00%”。说实话这类截图在刷题群里天天见可当它出现在自己的提交记录上时我还是忍不住想认真复盘一遍。这篇小记会把这轮“从能通过到跑进1ms”的过程完整拆开先聊聊0ms和击败100%的实际含金量再回到875这道题本身怎么解然后是我落地的四刀优化最后是跑出成绩之后的验证和复盘。无论你是刚开始刷题的小白还是正在冲刺极端性能的老手都能在里面找到一点能拿走的东西。1. 水落石出LeetCode的0ms到底有多少含金量1.1 计时精度只有1ms0ms更准确的名字是“查无此秒”LeetCode对运行时间的统计精度是1毫秒。显示的0ms并不是真的“零耗时”而是“这次执行时间小于1毫秒四舍五入归零了”。本质上0ms是一种查询不到具体耗时的状态我管它叫“查无此秒”。这不意味着代码被优化到了极限只说明它的常数已经小到连计时器都懒得记录。这个坑我早年踩过。第一次在Easy题上拿到0ms兴奋地跟室友吹了半天后来发现那道题哪怕用两层循环也能0ms——测试数据太小任何正常写法的耗时就都落在1ms刻度以内根本没法用这个指标区分好坏。我翻过自己的提交记录0ms出现频率最高的是两类一类是字符串拼接、数组翻转这种送分题另一类就是今天这种规模到位的中等或Hard题。前者的0ms是数据规模给的后者的0ms才是解法该抢的。1.2 击败100%的百分比本身就是个浮动的统计量那“faster than 100.00%”是不是代表我把所有提交者都踩在脚下了也不是。这个数据本质上是一个样本统计量基于的是评测服务器积累的同语言历史提交。问题在于样本会变服务器状态也在变。同样的代码我今天提交是0ms晚上再去交一次也许就是4ms同一份代码在不同人手里也可能一个人看到击败87%另一个人看到击败100%。我做过最无聊的验证把一份稳定通过的代码连交五次结果显示0ms、0ms、4ms、8ms、4ms击败比例从100%到73%都出现过。所以百分比更像是给你一个“当前这波样本里的位置感”跟绝对性能没有严谨的数学对应。另外百分比还受近期提交者水平分布的影响。如果一批人扎堆用更优解法去交同一个代码的百分位自然会被推到后面。这不代表你变弱了只代表样本变化了。1.3 什么样的0ms才真正值得庆祝所以0ms到底可不可信我的判断标准很简单题不是送分Easy解法本身有复杂度上的优势而且不是一次性重复提交依然稳定。三项都满足这个0ms才值得截图、值得复盘、值得写一篇小记。875这道题勉强满足前两条所以我决定把这次“能通过”到“跑进1ms”的过程完整拆开。整个复盘包括题面分析、四刀优化和跑出成绩之后的验证每个环节都有可复用的经验。2. 今天的主角LeetCode 875 爱吃香蕉的狒狒2.1 题面回顾Koko一小时只能专心吃一堆这道题在力扣中文站的题名是《爱吃香蕉的狒狒》题号875。题目给了n堆香蕉piles[i]表示第i堆有多少根。狒狒Koko每小时能吃k根香蕉但有个要命的限制它一个小时只能对着一堆吃哪怕这一堆只剩一根剩下的时间也不会转场去别的堆。所以“每小时吃k根”准确的理解是“最多吃k根且限制消耗对象是某一堆”。判断速度k是否可行需要对每一堆计算它需要的小时数ceil(piles[i] / k)。把所有堆的小时数加起来如果不超过总时长h就可行。题目还有一个隐含前提h一定大于等于堆数n。因为哪怕速度开到无穷大一小时最多也只能消灭一堆h小于n的时候无论如何无解。这个前提保证了二分上界可以安心取max(piles)不会出现无解的情况。我第一次读完题面脑子里冒出来的是最朴素的枚举法k从1开始逐个试每试一个就遍历全部堆累加小时数第一个满足条件的k就是答案。逻辑无懈可击但k的取值上限是max(piles)最大能到10^9再叠加上n最大10^4完全撑不住。2.2 单调性是这道题的破题钥匙这题真正的突破口是单调性。速度k越大吃完所有香蕉所需的总时间只会更短绝不会更长。于是“在h小时内能否完成”这个判断结果随着k从1增大会由false变成true而且只变一次。面对这种单调可分割的搜索区间二分查找就是标准答案。搜索范围不用乱想就是[1, max(piles)]。k超过max(piles)没有意义因为速度再大每堆也至少需要一小时kmax(piles)时总时间已经是最小值n小时了。判断某个速度m是否可行的过程里最需要注意的是不要引入浮点数。每堆耗时ceil(piles[i] / m)如果写成(double)piles[i] / m然后向上取整会有精度和性能双重损耗。正确姿势是整数运算(piles[i] m - 1) / m。这个式子的原理是给被除数补上m-1让除法结果自动向上取整。类比来说就像“把一个数往最近的m的倍数方向凑”补到能整除为止。为了验证边界逻辑我手算了一组示例piles [3, 6, 7, 11]h 8。速度4时四堆耗时分别是1、2、2、3小时总共8小时可行速度3时四堆耗时是1、2、3、4小时总共10小时不可行。答案就是4。这个例子能很好地检验check函数有没有写偏。另外聊一下二分模板的选择。网上二分写法五花八门左闭右闭、左闭右开、找左边界、找右边界第一次接触的人很容易绕晕。我个人的习惯是统一用[left, right]左闭右闭配合while (left right)收敛时返回left。判断mid可行时因为mid本身可能是答案所以right mid不可行时mid被严格排除所以left mid 1。这种写法最大程度避免死循环也适合875这种找最小可行值的场景。如果你习惯左闭右开那是另外一整套边界逻辑千万别混着写。2.3 朴素二分能跑到什么水平我第一版代码就是标准的“二分答案 check”写完一把过成绩大概是20ms左右击败60%。这个成绩和“0ms”之间还有明显距离。于是我开始逐项审视这20ms花在哪儿了。二分本身最多迭代约30轮每轮遍历n10^4大约30万次核心运算。在不算离谱的常数下C跑这个量级应该是几毫秒到十几毫秒。所以20ms说明常数还有水分iostream同步开销、check函数无脑遍历、类型和运算的选择都在拖后腿。下面这四刀每一刀单独拿出来都不算什么高深技巧叠加起来的效果却足够把结果顶到0ms。3. 从20ms到0ms我实际做的四刀优化3.1 第一刀断掉C标准流和C语言流之间的同步先说说C选手最容易忽略的隐藏开销。cin和cout默认会跟C语言的scanf和printf保持同步保证两种IO混用时不会错乱。这个同步机制在刷题场景毫无必要——我根本不会在同一段代码里同时用两套IO风格但它会拖慢每次cin/cout的执行。关掉它的办法是两句话ios::sync_with_stdio(false); cin.tie(nullptr);sync_with_stdio(false)让iostream不再和stdio做同步校验cin.tie(nullptr)则解除了cin和cout之间的关联。默认情况下cin和cout是绑在一起的每次用cin读数据前系统都会担心cout缓冲区里的旧内容还没输出会先去刷新cout这个连锁刷新非常费时。解绑之后读归读写归写输出量小的时候完全不冲突。我习惯用一个技巧在进入main之前就把这两步做完static const bool io_sync_off []() { ios::sync_with_stdio(false); cin.tie(nullptr); return true; }();这个写法利用静态变量的初始化时机匿名lambda在main执行之前运行返回true只是为了让编译器不报“未使用变量”的警告。加了这一刀之后875的成绩大概从20ms降到了12ms左右。3.2 第二刀用理论下界压缩二分区间二分查找的总轮数取决于区间长度。默认情况下搜索范围是[1, max(piles)]max(piles)最大能到10^9log2(10^9)大约是30轮。每少一轮相当于直接省掉完整的某轮check循环。怎么把下界往上抬我利用的是一道朴素的总量逻辑所有堆的香蕉总数是sum总时长只有h小时那么无论如何平均每小时至少得吃掉sum/h根香蕉。考虑到小时粒度是整数、最后一小时可能吃不满更严谨的下界是ceil(sum / h)也就是(sum h - 1) / h。如果某个k小于这个下界即使狒狒每一小时都满载运行总吞吐量也满足不了需求它完全没有可能成为答案。把这个下界塞进二分的left初始值区间长度被压缩迭代次数自然减掉几轮。极端情况下当数据里有一堆特别大时下界甚至会直接逼近上界二分几乎原地收敛。上面的示例piles [3, 6, 7, 11]h 8sum 27ceil(27/8) 4下界恰好就是答案。也就是说这道示例甚至不用二分直接返回下界就是对的。这跟之前推导的结果一致说明这个下界逻辑相当可靠。这一步之后成绩大概从12ms到了8ms附近。3.3 第三刀check函数里的提前终止二分的主体是check函数给定速度m累加每一堆需要的小时数和h比较。正统写法是老老实实把数组遍历完再返回但这里有一个很容易被忽略的观察我真正需要知道的只有“总小时数是否已经超过h”。一旦累计值越过h后面所有堆都不用再算了直接返回false。这个剪枝在二分过程中非常有用因为二分有一半左右的mid会落在不可行区域而这些区域里累计小时数往往很快超过h。比如速度过小的时候前几堆的耗时就是天文数字几轮加法就要跳出。加上break之后检查逻辑从“全量计算”变成“最多算到超时为止”实际遍历的堆数远小于n。对应结构像这样long long hours 0; for (int bananas : piles) { hours (bananas mid - 1) / mid; if (hours h) break; }我顺手把check判断内联进了循环省掉高频调用点的函数栈帧开销。对于这种每轮二分都要触发几十万次的调用点函数调用本身虽然不大但积少成多也值得消掉。这一刀加完成绩已经在4ms左右了。3.4 第四刀类型选对了数学才不会悄悄变质最后一刀看着不起眼但能决定你从4ms到0ms之间的路是否走得稳。题目数据范围里piles[i]最大10^9n最大10^4sum极限接近10^13int根本装不下。如果不小心把sum、hours这类变量定义成int在大数据用例下会出现溢出后的负数check函数直接给出错误判定。二分里还有两个常见的类型细节。第一中间值要写成left (right - left) / 2而不是(left right) / 2前者能防止两数相加时溢出。第二check内部的表达式(bananas mid - 1) / mid如果bananas是int而mid是long long加法时int会自动提升为long long通常是安全的但如果mid被定义成int那么大数据下bananas mid - 1本身可能溢出结果不可信。所以我全程用long long只有最后返回答案时才转回int。另外一个看似不起眼但值得记住的选择right取max(piles)而不是sum。速度超过max(piles)后总时间已经降到最小可能值n小时再往上提速没有任何收益只会白白增加二分轮数。类型修正本身不直接制造0ms但它保证了极端用例下代码不会悄悄算错。没有这层保证前面三刀优化得再狠也只是在错误的大厦上跳踢踏舞。3.5 最终代码与提交成绩四刀全部落地完整代码如下static const bool io_sync_off []() { ios::sync_with_stdio(false); cin.tie(nullptr); return true; }(); class Solution { public: int minEatingSpeed(vectorint piles, int h) { long long sum 0; long long maxPiles 0; for (int bananas : piles) { sum bananas; if (bananas maxPiles) maxPiles bananas; } long long left (sum h - 1) / h; long long right maxPiles; while (left right) { long long mid left (right - left) / 2; long long hours 0; for (int bananas : piles) { hours (bananas mid - 1) / mid; if (hours h) break; } if (hours h) { right mid; } else { left mid 1; } } return (int)left; } };提交之后页面直接弹0ms击败100%。我为了排除服务器运气又连交两次还是0ms。整个代码的时间复杂度是O(n log M)M是最大堆香蕉数空间复杂度O(1)。0ms的本质不是算法级别的飞跃而是把所有常数项都压到足够小小到运行时间跨不过1毫秒的刻度线。我把这条优化链路的典型耗时整理了一下方便你对照自己的实测情况优化阶段大致耗时主要收益朴素二分20ms正确性优先关闭IO同步12ms输入输出常数大幅下降理论下界压缩8ms二分迭代轮数减少check提前终止4ms不可行区间快速短路类型修正最终版本0ms稳定性保障跨过刻度线这些数字是我多次提交里挑的典型值不是精确实验数据。评测机的负载波动会带来1到2ms的浮动所以看趋势就好别把具体数值当成硬指标。4. 跑出0ms之后我反而会做这几件事4.1 用极端用例先捶一遍验证的不是性能而是正确性0ms的成绩容易让人瞬间自信但二分题的边界错误也最擅长在这些时刻偷袭。拿到0ms后我的第一反应不是庆祝而是把几组可能击穿边界的用例跑一遍。测试用例期望答案代码返回piles [3,6,7,11], h 844piles [30,11,23,4,20], h 53030piles [30,11,23,4,20], h 62323全为10^9, n10^4, h10^410^910^9中间两个用例很有意思。h 5时堆数也是5狒狒必须每小时消灭一堆速度至少要达到最大堆30答案因此锁定30h 6时速度23会让各堆耗时变成2、1、1、1、1总耗时6恰好可行而速度22则变成2、1、2、1、1总耗时7超了。这种灵敏度极高的对照数据最能暴露二分边界的偏差。最后那个大数据用例专门验证sum会不会溢出、运行时间是否仍可控。四个用例全部通过我才在复盘笔记里给了这次0ms一个“有效”的标签。4.2 把击败百分比扔掉回到复杂度本身0ms好看但它改变不了这道题的复杂度本质。这题的求解过程注定是“在一个值域上搜索”而值域上限最大10^9线性枚举完全不可行二分迭代到O(log M)层是数学上的铁律。在最优算法框架下进一步压榨只能靠常数因子而常数因子决定的是“击败百分比”而不是“复杂度类别”。我建议每个刷题人都养成一个习惯提交通过后把页面上的百分比从心里划掉问自己三个问题——我的算法是什么复杂度空间呢还能不能从算法层面继续降一个量级875的答案是O(n log M)、O(1)、不能从算法层面再降。这时候百分比的含金量才算有了坐标系。LeetCode热门题的题解区里二分答案的写法五花八门很多人会贴出自己的0ms代码。参考他们怎么调边界、怎么处理向上取整比抄一份代码有价值得多。尤其是875这种几乎每届刷题人都会做的高频题题解里的边界讨论几乎包含了二分题所有常见的坑。4.3 换个语言、换个姿势再写一遍0ms是C的专属浪漫换个语言体验会完全不同。我为了验证思路的普适性用Python把同样的二分逻辑写了一遍def minEatingSpeed(piles, h): lo, hi (sum(piles) h - 1) // h, max(piles) while lo hi: mid (lo hi) // 2 hours sum((p mid - 1) // mid for p in piles) if hours h: hi mid else: lo mid 1 return lo同样的逻辑Python在大数据用例下会跑出几百毫秒甚至可能超时因为语言解释器的常数开销摆在那里。但这不代表Python解法“更差”它只是没法靠常数取胜必须更加依赖算法复杂度本身。所以不同语言之间的击败百分比完全没有可比性跨语言比较是最没意义的事情之一。这段Python代码最大的价值是帮我确认整个优化链条里真正不可或缺的只有二分框架和向上取整公式。C里的IO优化、内联check、提前break都是把常数压到极限的“物理加速器”对思路本身没有任何影响。4.4 复盘这次赢在哪里又有多少运气成分把四刀摆开复盘这轮优化真正改变战局的是两个点输入输出同步关闭和check函数提前退出。前者把基线成本砍掉大半后者把不可行区间的计算量大幅缩减。理论下界压缩和类型修正属于稳定性保障它们不直接制造0ms但能防止你在大数据用例上翻车。至于从8ms到0ms那一步我必须诚实服务器有贡献。评测机负载、提交时段的波动都会影响结果。我有过连着三次0ms的经历也遇到过在另一道题上同样的写法只跑出4ms的情况。所以我的结论是0ms值得当一次成就记录但千万别把它当成衡量代码的唯一标准。这轮复盘做完我顺手把875的题解思路整理进了自己的二分模板笔记。每次遇到“求最小可行值”“求最大可行值”“答案域连续单调”这类关键词就直接套这套流程写check、定上下界、左闭右闭二分、收敛返回。近期连周赛里好几道题本质上都是这个模板换了一层皮。好了这轮0ms的复盘就到这里。说点题外话我自己这两年刷题下来最大的体会是LeetCode的击败百分比就像游戏的段位图标看着刺激但真正决定你水平提升的永远是提交之后敢不敢把代码拆开重来一遍的耐心。如果你也想挑战一次0ms先从这道爱吃香蕉的狒狒入手把二分模板练到条件反射再配上一套属于自己的IO和check函数优化套路。等你真的在某道题上看到0ms的时候就会明白那种感觉——还真的挺上头的。