1. Day 4 的由来从闷头刷题到按专题打深井LeetCode 打卡第四天最大的感受不是我会的题变多了而是终于摸到了套路的边。前三天我是典型的乱序刷题选手今天看到数组题就做数组明天遇到链表就切链表后天被一道字符串题卡得怀疑人生。结果呢题号记了一堆遇到新题照样无从下手。这种状态特别像我刚学做饭时的样子——菜谱背了二十道但真让我不看菜谱做一桌菜全乱套。因为菜谱是散的没有形成荤素搭配、先备菜再下锅的流程感。第四天我做了个重要调整不再随机挑题而是按专题进攻一次只打一口井。今天这口井的名字叫二分答案主菜就是 LeetCode 热门 100 题里的第 73 题——爱吃香蕉的狒狒对应原题编号 875。这道题绝对是二分答案专题的教科书样本因为它把最小化一个值的优化问题干净利落地转换成了给定一个值判断行不行的决策问题。这个思维转变一旦打通后续整个专题的题都会顺畅很多。1.1 为什么我把 Hot 100 当主线LeetCode 热门 100 题这个清单圈内评价一直两极分化。有人认为它太经典、不够前沿但对我这种准备面试、需要快速建立题型地图的人来说它几乎是必刷清单。原因很简单这 100 道题覆盖了面试里出现频率最高的思维模型——双指针、滑动窗口、单调栈、二分、动态规划、图论基础每一道都是某个套路的标准件。我在 Day 1 到 Day 3 踩过最大的坑就是见题刷题、不归类。数组题里有双指针字符串里也有双指针但我不归类就发现不了这个共性。Hot 100 的好处恰恰在于它是按经典模型而不是数据结构的表面标签来分布的。你刷到第 73 题的时候会发现它本质是二分而不是一道普通的数组模拟题。这个认知就是归类能力的雏形。1.2 Day 4 的练习清单怎么排今天的清单我做成了一小套递进结构不是只刷一道题前置热身先默写标准二分查找的两套模板确保找左边界和找右边界不会混。主菜875 爱吃香蕉的狒狒要求能在 20 分钟内独立写出来并且用不同语言各写一遍。加餐1011 在 D 天内送达包裹的能力同样的套路换了容器包装。佐餐刚好赶上周赛 430用里边的题目检验一下二分答案在实战里到底好不好使。这个安排的逻辑是先练肌肉记忆再练识别迁移。光看懂题解没用得靠大量重复让看到最小化 xxx 就反射性想到二分变成条件反射。2. 原题复盘LeetCode 875 爱吃香蕉的狒狒2.1 题目到底在说什么先讲人话。狒狒面前有 n 堆香蕉每堆有 piles[i] 根它每小时可以选择一堆吃掉 k 根。如果这一堆剩下的不足 k 根那它就把这一堆全部吃完然后这个小时剩下的时间它就不吃了对它不会去再开一堆。守卫走了h 个小时后会回来。问能让狒狒在 h 小时内吃完所有香蕉的最小整数速度 k是多少。举个具体例子piles [3, 6, 7, 11]h 8。如果 k 4每堆耗时分别是 ceil(3/4)1、ceil(6/4)2、ceil(7/4)2、ceil(11/4)3总耗时 8 小时刚好赶在守卫回来前吃完。如果 k 3耗时是 1 2 3 4 10 小时超了。如果 k 5耗时是 1 2 2 3 8 小时也能吃完但它不是最小的因为 4 已经可行了。所以答案不是找到一个能吃完的速度而是找到能吃完的最小的那个速度。这句话是整道题的题眼。2.2 从暴力法到二分答案思维转变过程很多新手拿到题第一反应是暴力枚举从 k 1 开始试算总耗时找到第一个满足条件的 k 就返回。这个思路一定对但一定超时。因为 piles[i] 最大可以到 10^9如果答案特别大枚举的次数就会非常恐怖再乘以每轮遍历 n 堆的开销最坏情况是 O(max(piles) * n)在 LeetCode 的数据范围下直接 TLE。那怎么优化关键在观察总耗时和速度之间的关系。设想我们把速度 k 从 1 一路往上加总耗时 f(k) 会怎么变化肯定是不增的——吃得越快花的时间越少这不是什么高深数学就是生活常识。这个单调性才是二分的灵魂。有了单调性题目就从在无限空间里找最优解变成了在一个有序的布尔序列里找分界线。我们定义一个 check(k)按照速度 k 能不能在 h 小时内吃完。那么 k 从小到大的 check 结果就是一堆 F、F、F、T、T、T……我们要找的答案就是第一个 T 的位置。而在一个单调序列里找第一个满足条件的位置这正是二分查找最擅长的事。这个把优化问题翻译成决策问题的过程就叫二分答案。我特别喜欢这个题还有一个原因它的 check 函数非常直观不需要复杂的数学推导只是老老实实地把每堆耗时加起来而已。2.3 核心代码与复杂度分析直接上 Python 实现代码非常短class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: left, right 1, max(piles) while left right: mid (left right) // 2 hours sum((p mid - 1) // mid for p in piles) if hours h: right mid else: left mid 1 return left这里 (p mid - 1) // mid 是向上取整的经典写法。比如 p 11mid 4那 (11 3) // 4 3正好是 ceil(11/4)。复杂度分析外层二分次数是 O(log(maxP))maxP 是最大堆的香蕉数每次 check 要遍历全部 n 堆所以总复杂度 O(n * log(maxP))空间 O(1)。这个复杂度在数据范围下非常轻松跑得飞快。3. 二分答案的完整模板与细节拆解3.1 两套模板的区别与选择很多人在二分这里翻车翻车原因永远不是不会二分而是模板混用。我见过身边不少朋友把找左侧边界和找右侧边界的模板背串结果在边界上调半天。这里我把两套最常用的模板整理成一张对照表模板适用场景核心写法注意点左闭右闭 答案变量找到某个值或最后一个满足条件的位置while l r满足条件时记录 ans 并收缩区间容易在收缩方向写反左闭右开 区间收敛找第一个满足条件的位置while l r满足时 r mid不满足时 l mid 1mid 必须用下取整不能 1875 这道题属于找第一个满足条件的位置所以用第二套模板最自然left 指向一定不行的区域外right 指向一定可行的区域。每次把 mid 塞进 check如果可行就把 right 收回来如果不可行就把 left 推上去。循环结束时 left 和 right 重合那个位置就是答案。换句话说布尔数组是 FFFTTT我们要的是 F 和 T 之间的那条缝这个缝就是 left 最终停下的地方。3.2 check 函数怎么写才不容易错这道题的 check 函数只有一行核心逻辑但有几个容易写错的地方。第一向上取整不要用浮点。有人图省事写 math.ceil(p / mid)这在数值小时没问题但 p 和 mid 都是大整数时浮点精度会让结果产生 1 的误差而且多一道类型转换性能也不如整数运算。遇到这种向上取整我一律用 (p mid - 1) // mid纯整数运算又快又稳。第二check 里的小优化我们其实不需要算完所有堆的耗时一旦累计 hours 已经大于 h就可以提前 return False 了。这在数据量大时能省不少时间尤其是二分后期 mid 很小时几乎第一堆就超时了。写成这样def check(speed: int, piles: List[int], h: int) - bool: total 0 for p in piles: total (p speed - 1) // speed if total h: return False return True第三别把 hours h 写成 hours h。题目要求在 h 小时内吃完恰好用完 h 小时是允许的。这个等号丢掉的后果是答案会凭空大 1而且样例都不一定测得出来非常阴险。3.3 整数溢出与其他语言陷阱Python 用户在这道题上很幸福int 无限大随便算。但如果你在用 Java 或者 Chours 这个变量就一定要用 long。为什么piles 最多 10^4 堆每堆最多 10^9 根香蕉如果 k 很小hours 理论上能累积到 10^13 这个量级int 上限才 21 亿左右直接爆。我最初用 Java 写的时候就是 int total一提交就 WA把 total 改成 long 立刻 AC。另一个细节是二分的右边界。有人图省事把 right 设成 sum(piles)这在数学上没问题但没必要——速度大于等于 max(piles) 时每堆最多一小时就吃完了再大速度没有意义。直接用 max(piles) 当上界二分范围更小、收敛更快。还有个小坑left 一定从 1 开始不要从 0 开始。左边界为 0 时check 里 (p 0 - 1) // 0 直接除零崩掉。这个错误低级但真实我见过不止一个新手掉进去。4. 把二分思想迁移到周赛 430 与同类题4.1 周赛里的最小可行值套路Day 4 刚好撞上周赛 430 的赛程我打完之后最大的感触是竞赛题和经典题之间的墙比想象中薄得多。周赛里常见一类题描述五花八门给你一个数组让你做一些操作问最少操作几次能达成某个条件或者最小的某个阈值能保证 xxx。很多人在赛场上看到这种题第一反应是贪心或者 DP然后陷入细节调不出来。但如果你刚刷完 875脑子里应该立刻弹出来一个问题这个量是不是单调的如果我猜一个答案能不能写一个 check 快速验证比如一些题答案的可能范围是 [1, max]check(mid) 的意思是在限制为 mid 时能否完成目标条件天然满足单调性。这时候就是二分答案的完美猎物。我在周赛复盘时发现赛后题解里二分答案 check的解法一抓一大把而我自己在赛场上却绕了远路——这就是典型的不熟悉套路导致识别不出来。所以我的建议是周赛的价值不只在 AC 数量更在于赛后用经典题的目光去重新审视每一道题。你会发现 Hot 100 练的东西在真实比赛中是直接能用的这种经典题没白刷的反馈比任何打卡激励都管用。4.2 同类题串讲一个套路多种包装二分答案最有意思的地方在于同一个套路能套进完全不同的故事背景里。我从 Hot 100 和相关题目里挑了三个典型的放在一起对比看题目二分对象check 函数单调性来源875 爱吃香蕉的狒狒吃香蕉速度 k总耗时是否 h速度越大耗时越少1011 在 D 天内送达包裹的能力单日运载能力 cap所需天数是否 D运力越大天数越少410 分割数组的最大值子数组和的最大值 limit能否在 m 段内分完limit 越大分完所需的段越少以 1011 为例核心思路一模一样二分运载能力猜一个 cap然后从左往右贪心地装包裹统计需要多少天如果天数 D 就说明 cap 可行否则不可行。唯一的区别就是把吃香蕉耗时换成了运输天数把每小时一堆换成了每天必须按顺序装。我在刷 1011 的时候还发现一个细节差异875 的左边界固定是 1但 1011 的左边界必须是 max(weights)因为任何一天的运载能力如果小于单件包裹的重量这件包裹就永远送不出去。这类隐藏约束是二分答案题的第二道陷阱单靠模板是发现不了的。4.3 怎么一眼识别该用二分答案这个能力比多刷十道题都值钱。我的经验是看到题目同时满足下面三条就可以优先考虑二分答案第一条问题是最小化 xxx或最大化 xxx且答案是一个有限范围内的整数。比如最小吃香蕉速度、最小运载能力、最小分割上限。第二条存在一个天然的 check 函数也就是给定一个候选答案能在多项式时间内验证它是否可行。这个验证过程往往伴随一次贪心扫描或者简单累加。第三条候选答案和验证结果之间有单调性。这一步最关键也是很多人忽略的。你需要先证明答案增大或减小时check 的结果只会从 False 变 True 或者反过来不会忽 True 忽 False。一句话总结题目问最值答案有界check 好写具备单调——四个信号凑齐三个以上直接往二分的路子想。5. 常见 bug 排查与调试技巧实录5.1 问题速查表刷这类题最容易踩的坑其实高度重复排成一张速查表贴屏保都行症状根因解法提交后超时check 没有提前剪枝全量求和累计超过上限立即 return false答案比正确值大 1边界条件用了 而不是 检查恰好耗尽 h 小时是否允许答案比正确值小二分右边界取小了确认上界是 max(piles) 或 max(weights)死循环不退出mid 计算方式与区间收缩方向不匹配统一用 l (r - l) // 2检查收敛方向Java/C 答案异常大hours 用 int 存储溢出了中间量改用 long运行时除零左边界从 0 开始左边界从 1 或业务下界开始5.2 一次真实的翻车记录这里分享一个我自己的真实 debug 过程。用 Python 写 875第一版我写成这样l, r 0, max(piles) while l r: mid (l r) // 2 if sum((p mid - 1) // mid for p in piles) h: r mid else: l mid 1 return l一运行直接 ZeroDivisionError。当时我还有点懵看了看报错行才反应过来left 初始是 0第一次 mid (0 11) // 2 5check 能过然后 r 变成 5接着 mid (0 5) // 2 2也正常问题在于如果一开始返回 False比如某些用例下 mid 可能会落回 0然后第二行 p // 0 当场爆炸。所以 left 必须从 1 起步最好顺手把 right 也压到 max(piles)减少无谓的迭代。第二版我又踩了个逻辑坑。我把 check 条件从总耗时 h写成了总耗时 h样例全过但提交 WA 在某个隐藏用例上。原因是这个用例刚好要求狒狒在 h 小时内恰好吃完而我把这个合法情况排除了导致答案整体上偏大。找了好久才通过肉眼对比发现等号丢了——这种边界错误最坑人因为它不在每个样例上都爆发。排查这类问题我的经验是WA 之后不要急着翻题解先把测试用例往极端方向构造。比如 h 等于堆数、piles 全是 1、piles 里有一个特别大的数。这三类用例基本能覆盖二分答案题 80% 的边界错误。5.3 用暴力解当裁判给二分答案做校验这里分享一个我强烈推荐的调试习惯写一个暴力参照函数和二分答案版本在随机数据上对拍。思路很简单。暴力版就是枚举 k 从 1 到 max(piles)逐个验证虽然慢但正确性一目了然。然后用随机生成的 piles 和 h 去跑两版结果一旦发现不一致立刻定位问题。这个办法在刷题阶段特别好用尤其是你对某个边界条件拿不准的时候。import random def brute(piles, h): for k in range(1, max(piles) 1): hours sum((p k - 1) // k for p in piles) if hours h: return k return -1 def binary_search(piles, h): l, r 1, max(piles) while l r: mid (l r) // 2 if sum((p mid - 1) // mid for p in piles) h: r mid else: l mid 1 return l for _ in range(10000): n random.randint(1, 20) piles [random.randint(1, 100) for _ in range(n)] h random.randint(n, 100) assert brute(piles, h) binary_search(piles, h) print(all ok)对拍跑 10000 组随机用例如果全过基本可以放心提交。这比你自己脑补边界条件靠谱一百倍。后来我做 1011、410 的时候也直接用这套对拍框架改一下 check 函数就能复用省了很多事。6. Day 4 收尾二分答案之外我学到的三件事说实话第四天给我最大的收获不是会了 875 这道题本身而是三件比题更值钱的事。第一套路不是贬义词它是经验的压缩包。前三天我总觉得 AI 味重的教程里讲套路很虚但自己刷到第四天就明白了二分答案、双指针、单调栈这些名字背后都对应着一类被反复验证过的思维路径。你不需要每次从零发明解法你需要的是快速识别题目的骨架然后往骨架里填肉。第二刷题的量要建立在复盘的质量上。一道题刷完如果只是AC 了就划走等于白刷。我会强制自己回答两个问题这道题卡在哪一步我这个思路能不能迁移到上一周做过的那道题上答不上来就回去重刷。Day 4 的 875 和 1011 放在一起对比之后我对二分答案这个模型的记忆深度比单独刷十道题都深。第三也是今天最后想分享的一个小技巧写题解。不是写给别人看的那种正式题解而是用几句话把这个题的思路讲给自己听。我在 Day 4 复盘时写的一句话是找最小值就猜一个值然后验证验证结果跟着猜的值单调变化——这就是二分答案的生活原型你猜一个速度跑得动就再猜慢点跑不动就猜快点直到找到刚好跑不动的那个临界点。 把这个人话版本写下来之后我发现自己对二分答案的理解突然就立体了。明天是 Day 5我计划进入双指针与滑动窗口专题正好把前几天的二分单调性和窗口收缩再串一串。刷题这事贵在细水长流。第四天阶段性及格。