记录一下刷题第四天。这一天我把LC073“爱吃香蕉的狒狒”翻来覆去看了很久也是因为这道题我才真正把二分查找从“背模板”变成了“能想明白”。如果你也在刷LeetCode热门100题或者刚开始系统的题解训练这道题很值得停下来认真啃一遍。它表面上是个“猴子吃香蕉”的趣味场景内核却是一道非常标准的二分答案题难度适中边界条件刚好够练手作为第四天的学习素材非常合适。很多人在第四天这个节点容易陷入“题刷了不少但感觉什么都没留下”的焦虑我自己也有过。所以第四天我没有急着开新题而是选了一道能贯通多种知识点的题目把暴力枚举、二分查找、整数边界、检查函数设计一次聊透。这篇文章不打算复述官方题解而是按照我实际踩坑的顺序把整道题从读题到AC的过程完整还原出来。1. 第四天我为什么选了一道“吃香蕉”的题1.1 从题目场景看它真正在问什么“爱吃香蕉的狒狒”题目描述看起来像童话故事狒狒有n堆香蕉第i堆有piles[i]根香蕉狒狒一小时能吃k根但一次只会选一堆吃而且如果某一堆剩下的香蕉不足k根它也只会吃掉这一堆然后这一小时内不再吃其他堆。现在要求在h小时内吃完所有香蕉问最小的k是多少。这个场景绕了一圈核心其实是数学问题给定一个速率k能不能在h小时内完成全部消耗然后找到满足条件的最小的k。我第一遍读题时犯了一个经典错误还以为狒狒可以多堆同时吃。如果允许跨堆计算那每小时的消耗量就是固定k总时间等于总根数除以k题目就变成了一个简单的除法问题。但题目明确说“一次只选一堆”每一堆花的时间实际上是向上取整的piles[i] / k小时不能把不同堆的剩余时间合并。这是题目设计里最容易被忽略的坑也是理解检查函数的关键。第四天选这道题还有一个私心它属于典型的“答案具有单调性”的题型。k越大吃完所有香蕉所需的总时间越小k越小总时间越大。这种单调关系正是二分答案法能够成立的前提条件理解了这个前提后面做其他二分题就能举一反三。1.2 为什么把二分法放在刷题第四天刷题计划前三天我都在做数组遍历、哈希表这类“线性思维”的题目到了第四天需要引入一个新的算法范式。二分法看起来语法简单左右指针加一个while循环但真正难的是判断“能不能二分”和“怎么构造单调函数”。我刻意选了这道题作为二分入门因为它比“猜数字”那种模板题多了一层抽象又比“旋转数组找最小值”少了很多复杂分支逻辑。它照顾到了二分学习的三个核心要点边界选择、循环不变量、检查函数设计。如果第一天就上来刷旋转数组很容易被各种边界条件劝退但先刷一道吃香蕉把最基础的“对答案二分”练扎实后面的路会顺很多。另外这道题在LeetCode热门100题里也是常客。它的变体很多比如“在D天内送达包裹的能力”“分割数组的最大值”本质上都是同一个套路题目要求某个最小可行值而这个值的可行性随参数变化呈单调趋势。先吃透一道题等于提前掌握了四五道题的解法。2. 题目拆解先想清楚“能不能”再想“最小是多少”2.1 检查函数是整道题的灵魂拿到这道题我并没有直接去写二分而是先把“给定k能不能吃完”这个判定过程单独抽出来。这一步非常关键。因为二分查找本身不关心吃香蕉的具体过程它只关心某个答案是否可行所以必须有一个足够快速、足够准确的判定函数。判断逻辑很简单如果狒狒的吃速是k那么对任意一堆香蕉吃掉它所花的小时数是ceil(piles[i] / k)。把所有堆的时间加起来如果总时间不超过h就说明这个k可行。这里有一个隐藏细节为什么是向上取整因为题目设定是狒狒一小时最多吃k根如果这一堆只剩3根而k等于5它不是停下来等下一小时而是吃完这3根后这一小时就结束了。从结果来看每一堆贡献的时间就是(piles[i] k - 1) / k小时。这个整数公式比调用浮点函数更安全因为浮点除法和向上取整结合时容易出现精度误差尤其在数据范围很大的情况下。我建议把检查函数单独抽出来写命名成canFinish(piles, h, k)这样后续调试时可以单独打印验证。很多新人喜欢把检查逻辑直接塞进while循环里一旦结果不对根本分不清是二分边界错了还是判定逻辑错了。分开之后问题定位会清晰很多。2.2 吃香蕉为什么不能用“平均速度”算把题目抽象成数学表达时有一个很容易踩的坑用总根数除以h当答案。比如总共有10堆香蕉共50根要求10小时内吃完有人会觉得速度是5根每小时。但实际因为一次只能吃一堆如果某一堆有49根而剩下9堆每堆只有1根吃速为5时49根那一堆就要吃掉10小时剩下的9堆根本来不及。所以平均速度只是理论下界不是可行答案。这个反例让我意识到二分答案的“答案空间”并不是连续的数学速率而是离散的整数k而且题目限制k至少为1吃速为0没有意义。理解这一点后初始搜索区间的下界就可以确定为1。上界则更简单一个人一小时最多吃一整堆如果k等于所有堆中最大的那一堆的数量它吃掉每一堆最多花1小时总共正好n小时。由于题目保证h不小于堆数所以k取最大值一定可行。很多人会问上界能不能取所有香蕉的总数当然可以但那样会扩大搜索范围白白增加一两次比较。取最大值既保证可行又尽量压缩区间是性价比最高的选择。3. 从暴力枚举到二分查找完整实现过程3.1 先写一版能跑通的暴力解为了验证对题目的理解我第一步写的是暴力枚举从k等于1开始逐个测试直到找到第一个能满足时间限制的k。这个解法最坏情况下要枚举到堆中的最大香蕉数假设最大堆有10^9根而h很小枚举次数会非常恐怖直接超时。但写暴力解并不是白费功夫。它能用来验证检查函数写得对不对还能在二分实现之后作为对小数据集的基准答案。我在本地测试时专门的对比脚本先跑暴力解得到正确结果再跑二分解对比输出。这样即使二分代码写出了边界问题也能立刻发现而不是等到提交超时或者WA时再一头雾水。暴力解的核心代码大概长这样def minEatingSpeedBruteForce(piles, h): max_speed max(piles) for k in range(1, max_speed 1): total_hours sum((pile k - 1) // k for pile in piles) if total_hours h: return k return max_speed这个版本的检查逻辑和二分版本完全一致只是k的取值是线性搜索。通过它我确认了两件事第一检查函数确实正确第二确实存在一个最小的k满足条件。确认之后才放心进入二分实现。3.2 二分法实现与三个细节二分法的思路是在1到max(piles)之间寻找最小的可行k。每次取中间值mid调用检查函数如果mid可行说明答案可能更小把右边界收缩到mid如果mid不可行说明答案必须更大把左边界收缩到mid1。当左右指针相遇时指针值就是答案。from typing import List def minEatingSpeed(piles: List[int], h: int) - int: def can_finish(k: int) - bool: hours 0 for pile in piles: hours (pile k - 1) // k return hours h left, right 1, max(piles) while left right: mid (left right) // 2 if can_finish(mid): right mid else: left mid 1 return left写完这段代码我盯着while循环的条件看了半天。这里最需要想清楚的是left right和left mid 1的配套关系。因为可行时右边界直接收到mid不可行时左边界收到mid1所以循环结束后left一定等于right而且这个值一定是一个可行解同时不可能存在比它更小的可行解。还有一点容易被忽略mid的计算方式。虽然Python里(left right) // 2不会溢出但如果你用Java或C写left和right很大时相加可能溢出。建议养成写left (right - left) // 2的习惯。这个细节在LeetCode题解里经常有人讨论属于那种“平时没注意面试被问一次就记住了”的知识点。3.3 复杂度对比暴力与二分的实际差距我很喜欢用一个具体数字来感受两者差距。假设piles数组长度n等于10^4最大堆有10^9根香蕉。暴力枚举最多尝试10^9次每次计算要遍历整个数组总操作量是10^13级别在LeetCode的评测环境下几乎必然超时。二分查找只需要log2(10^9)次约30次检查每次检查遍历一遍数组总操作量是30乘以10^4也就是30万次操作。这个差距从几十分钟级别骤降到几毫秒级别。方法检查次数每次检查开销总时间复杂度实际表现暴力枚举O(max(piles))O(n)O(n × max(piles))大数据直接超时二分查找O(log max(piles))O(n)O(n log max(piles))稳定通过因为检查函数是O(n)整体的时间复杂度是O(n log max(piles))空间复杂度O(1)。这个复杂度在LeetCode的题解分类里属于很标准的优秀解也是大多数题解会给出的方案。4. 现场实录我踩过的四个边界坑4.1 吃速下界选0导致的除零问题我第一版代码写的left是0想着速度可以为0。结果检查函数里做除法直接报错才意识到速度的下界必须是1。这个错误很典型因为很多二分题的搜索区间下界确实是0但这道题里速度0没有实际意义。从数学上讲k是每小时吃掉的根数最小只能是1从工程上讲除数为0在任何语言里都是非法操作。我在本地写单元测试时用例覆盖了piles[3, 6, 7, 11], h8这种最小规模的输入除零错误很快就被暴露出来了。这个问题也提醒我一个通用经验二分的边界值选取不能照搬模板要先思考这个值在实际问题中代表什么。比如“在D天内送达包裹”那题下界是所有包裹中的最大值而不是0再比如“分割数组的最大值”那题下界也是数组中元素的最大值。边界的具体值取决于题意不是所有题都从0开始。4.2 上界选择max还是总和的纠结我提交时被一个测试用例逼着重新想了一遍上界。当piles是[1, 1, 1, 1]h是4时答案显然是1。当piles是[1, 1, 1, 1000000000]时max直接就是10亿这个上界看起来很大但实际上没有任何浪费因为二分只需要30次迭代就能收敛。我还试过把上界设为sum(piles)在数据特别大时比如总香蕉数是10^14虽然只多了30多次迭代但没有任何必要。关键是max(piles)这个上界对应的是“一小时只吃一整堆”的物理意义如果吃速达到最大值每一堆都恰好花一小时总时间正好等于堆数n而题目条件保证h大于等于n因此这个值一定可行。想清楚这层逻辑后我坚定地选择max作为上界。4.3 while left right 和 的混乱很多二分题解里能看到while left right配合left mid 1和right mid - 1的写法也有while left right配合left mid 1和right mid的写法。两套模板都能跑通但不能混用。我一开始习惯用left right的模板从力扣的“搜索插入位置”那道题带过来的习惯在这道题上就出了岔子。问题出在“左边界可行时右边界收不收回mid减一”上。如果我们把可行解保留在区间内希望最后区间收敛到一个点那么用left right是最直观的。一旦换成就要在可行分支里写成right mid - 1同时需要一个额外的变量维护答案代码就变得绕。现在我统一用“区间内保留候选答案”的写法遇到一道题就固定用一种模板不再混用。4.4 检查函数里求和为什么不能用浮点数写检查函数时我第一反应是调用math.ceil(pile / k)在Python里这样写也能得到正确答案但我后来看讨论区题解时发现一个有意思的点浮点运算可能因为二进制精度问题导致细微偏差。尤其在pile和k都是很大整数时pile / k的浮点结果可能略低于真实商再向上取整就会导致小时数少1整个检查结果错掉。为了避免这类问题我改成纯整数运算(pile k - 1) // k。这个写法模拟了向上取整而且完全不依赖浮点数。在LeetCode的评测数据里浮点版本的提交可能也能通过但一旦题目数据范围变得更极端这种隐患就会暴露。我的原则是能用整数运算就绝不用浮点。5. 从一道题延伸出的刷题方法论5.1 怎么识别“二分答案”类题型刷完这道题后我给自己总结了一套判断标准如果题目中出现“求最小的最大值”“求最大的最小值”“在满足条件的前提下求最小可行值”这类描述大概率就是二分答案题。这个识别过程可以拆成三步第一步确认答案具有单调性。在这道题里k增大总时间减小方向可能不同但一定单调。第二步确认检查函数可以快速实现。我们能在O(n)时间内判断某个k是否可行这是二分成立的效率基础。第三步确认搜索区间可以确定。下界和上界都能通过逻辑推理得到具体值而不是依赖猜测。这套标准适用于很多题。比如“每个包裹必须按顺序运出在D天内送完求最小载重”载重越大需要的天数越少再比如“把数组分成m个子数组求各子数组和的最大值最小化”子数组和上限越大能分出的子数组数量越少。它们都是同一个套路。5.2 第四天刷题节奏安排与一点体会第四天我一共安排了四道题分别是“爱吃香蕉的狒狒”“在D天内送达包裹的能力”“分割数组的最大值”“寻找旋转排序数组中的最小值”。前两题练二分答案第三题练二分答案加贪心检查第四题练传统二分搜索。这个组合的好处是循序渐进从“判定某个值是否可行”到“搜索某个特定值”没有一道题是重复劳动。我自己的刷题节奏是把每道题分成三个步骤先不看题解独立写15到20分钟写不出来就去看两到三篇题解看懂后合上答案再写一遍最后隔一天用相似题型检验。第四天的收尾练习是参加了一次周赛虽然没有全部AC但遇到一道很类似二分思想的题目时我明显感觉到自己的反应速度快了不少。这种“以前会卡住现在好像有点感觉”的变化就是刷题计划继续下去的动力。如果你也在做LeetCode热门100题的计划我建议不要追求一天刷很多题尤其是第四天到第七天这个阶段知识密度开始变大一天两到三道题并吃透每道题的检查函数设计比刷十道题然后全部忘记要好得多。我笔记本上写着这么一句话“刷题的数量决定视野刷题后的总结决定水平。”第四天这道“爱吃香蕉的狒狒”让我对这句话体会特别深。