如果你也在刷 LeetCode 热题100那应该对第073题——爱吃香蕉的狒狒力扣原题号 873不陌生。我最初看到这道题时第一反应是香蕉、狒狒、每小时吃多少根这跟算法有什么关系直到真正动手做了一遍才意识到这是把“二分答案”这个套路讲得最透彻的一道经典题。热题100里能同时覆盖二分查找、边界条件、整数溢出这三个高频考点的题目并不多它算一个。这篇是系列第五篇我不打算泛泛罗列题目清单而是干脆拿它当主菜把一道题从题意拆解到代码落地再到坑点排查完整过一遍。无论你是刚开始刷热题100还是已经刷到一半卡在二分这类题上这篇都能帮你把思路理顺。1. 热题100到底在考什么先把清单看穿1.1 热题100的构成与真实定位很多人以为 LeetCode 热题100就是“100道简单题”这是个误解。它的实际构成是力扣根据面试频率、讨论热度、大厂题库交叉覆盖情况筛选出的100道题难度分布大致是简单题约20%中等题约60%困难题约20%。覆盖的考点包括数组、哈希表、双指针、滑动窗口、二分查找、链表、二叉树、回溯、动态规划、贪心、图论、堆、单调栈等。它不是让你背题而是让你通过这些题目把常见的算法模板和思维模型全部过一遍。从刷题节奏上看热题100更适合作为面试前的集中冲刺清单而不是新手的第一本算法入门书。我见过不少同学一上来就按题号从1刷到100刷到第20题左右就开始迷茫因为不同专题之间跳跃太大前一道题还在做哈希表后一道题就跳到动态规划思维切换成本极高。我自己推荐的打开方式是先按专题分组每个专题集中刷4到6道题吃透共性套路之后再进入下一组。第073题爱吃香蕉的狒狒属于二分查找专题里最关键的一道因为它足够简单却把二分答案的核心逻辑暴露得很完整。1.2 二分查找题型的“题眼”在哪里二分查找这个考点在热题100里并不只有一个形态。大致可以分成两类第一类是“在一个有序数组里找一个数”比如经典的二分模板题第二类是“答案在一个单调区间里对答案本身做二分”这就是所谓的“二分答案”。爱吃香蕉的狒狒属于后者而且是非常典型的后者。判断一道题该不该用二分答案有一个很实用的标准如果题目里出现“满足某个条件的最小值”或“最大值最小化”并且这个条件的满足情况随着某个变量是单调的那就可以考虑二分答案。回到狒狒这道题速度K越大吃完所有香蕉所需的总时间就越短这是一个不严格递减的关系满足单调性求的是“在h小时内吃完的最小速度”这是“最小可行值”。两个特征都踩中了自然就锁定二分答案。我在给别人的建议里反复强调不要看到“二分”就只想到排序数组。很多题目不会直接给你一个有序数组但会给你一个单调的隐藏关系。抓住单调性才是二分题型的真正题眼。2. 073爱吃香蕉的狒狒把生活场景翻译成算法模型2.1 原题回顾与题意拆解先看原题描述狒狒面前有 N 堆香蕉第 i 堆里有 piles[i] 根香蕉狒狒每小时可以吃掉一堆香蕉中的 K 根。如果这一堆剩下的香蕉不足 K 根它就吃掉整堆并且这一小时内不会再去吃其他堆。警卫离开了 h 小时狒狒要在 h 小时内吃完所有香蕉求最小的 K。这里有几个信息需要准确翻译成算法语言。第一“每小时只能选择一堆”意味着一堆香蕉不管剩多少至少要花掉1个小时第二“每小时吃掉K根”是一种上限速度实际吃掉的数量是 min(K, 当前堆剩余根数) 向上取整第三“吃完所有香蕉”意味着所有堆都要被处理而不是只吃其中一部分。把这些翻译过来给定速度 K对于某一堆 p消耗的时间是 ceil(p / K)也就是 (p K - 1) / K 的整数除法结果。我见过有人在这个地方理解出错以为狒狒可以同时在多堆之间切换或者以为吃不完的可以剩到下一堆继续吃。这两种理解都会导致后面的计算完全跑偏。这道题所有细节都在“每小时只能吃一堆、吃不完也要占满一小时”这个设定上一旦忽略代码写得再漂亮也是错的。2.2 核心洞察为什么答案可以二分理解了题意之后最核心的一步是确认答案具有单调性。设 f(K) 表示速度取 K 时吃完所有香蕉需要的总小时数那么当 K 增大时f(K) 只可能变小或保持不变不可能变大。比如速度从2提到3原来需要吃 2 个小时的那堆现在可能只需要 1 个小时总时间不变或减少绝不会增加。既然 f(K) 单调不增那么“f(K) h”这个条件也具备单调性一旦某个速度可行再大的速度一定也可行一旦某个速度不可行再小的速度一定也不可行。这时整个速度区间就呈现出一个明显的分界点小于某个值的不可行大于等于某个值的都可行。我们要找的答案正是这个“临界值”。这就是二分答案能在 O(log R) 时间内完成搜索的根本原因R 是速度的上界。相比于直接从 1 开始逐个尝试这种对答案空间的折半搜索把时间复杂度从 O(R × N) 直接降到 O(N × log R)是一个数量级的提升。很多同学刷题时总觉得二分模板背下来就行忽略了“为什么能二分”这个前提遇到陌生的题目就判断不出来。这道题的价值恰恰在这里它把二分的前提条件用一道生活化的场景包装好了让你在轻松的氛围里把单调性这件事刻进脑子。3. 从暴力到二分完整解题实战记录3.1 暴力写法与超时教训我一开始尝试的是暴力解法代码很直白从 K 1 开始依次测试每个速度是否能在 h 小时内吃完找到第一个满足条件的 K 就返回。def minEatingSpeed(piles, h): n len(piles) for speed in range(1, max(piles) 1): hours 0 for p in piles: hours (p speed - 1) // speed if hours h: return speed思路没有任何问题但提交之后在极端数据上会超时。假设 piles 的长度是 10^4每堆最多有 10^9 根香蕉那么速度最大可能到 10^9外层循环要执行 10^9 次每次还要遍历一遍所有堆计算量完全不可接受。这个教训很典型暴力解经常能帮我们验证思路但它只适合小规模数据一旦数据范围拉满就必须用更聪明的算法。如果你去分析赛事或面试题的测试数据会发现出题人不会让暴力轻易过关。热题100里的中等题几乎都有类似的“隐藏屏障”数据范围大到你不得不优化。看到 N 在 10^4 到 10^5 级别、数值在 10^9 级别脑子里要立刻拉响警报O(N^2) 大概率超时需要往 O(N log M) 这类复杂度去想。3.2 标准二分答案模板暴力解法超时之后我换成了二分答案。需要明确搜索区间速度的最小值是 1最大值是 max(piles)。为什么不是 sum(piles)因为当速度等于最大堆的根数时狒狒每堆都需要花费正好1小时总时间已经等于堆数 N不可能更少了。速度再大对总时间的削减也有限不会低于 N 小时。所以上界取 max(piles) 已经足够覆盖答案。Python 实现如下def minEatingSpeed(piles, h): left, right 1, max(piles) def can_finish(speed): # 计算以 speed 吃完所有香蕉所需的总小时数 hours 0 for p in piles: hours (p speed - 1) // speed return hours h while left right: mid left (right - left) // 2 if can_finish(mid): right mid else: left mid 1 return left这里的核心就是标准的“找左边界”模板。由于我们要找的是最小可行速度所以当 can_finish(mid) 为真时说明 mid 是可行的但左边可能还存在更小的可行值因此把右边界收缩到 mid当 can_finish(mid) 为假时说明 mid 太小了答案一定在 mid 右侧因此把左边界收缩到 mid 1。循环结束时left 指向的就是第一个可行的速度。需要特别注意的是 mid 的计算方式写成 left (right - left) // 2而不是 (left right) // 2。虽然大多数情况下两者结果一样但 left right 在极端情况下可能溢出C 和 Java 的 int 类型尤其容易踩这个坑而 left (right - left) // 2 永远安全。这个细节在笔试题里可能不致命但在面试现场被追问时能准确说出为什么这样写很加分。3.3 边界处理与细节校对二分模板本身不复杂真正容易出错的是计算 hours 时的向上取整。我见过一些初学者写成 hours p // speed然后发现答案总是不对。原因很简单当 p 不能被 speed 整除时p // speed 会向下取整相当于少算了时间。比如一堆有 7 根香蕉速度是 3实际需要 ceil(7 / 3) 3 小时但整数除法 7 // 3 只给 2这就会导致计算出的小时数偏小可能把一个本不可行的速度误判为可行。正确的写法是 (p speed - 1) // speed这就是数学里的向上取整公式。推导过程也很简单ceil(a / b) (a b - 1) // b对所有正整数 a、b 都成立。建议把这个公式当作固定套路记下来因为涉及分配、装载、耗时计算的题目里经常用到记住它能省去每次重新推导的时间。还有一个小细节边界条件里 left 初始值取 1而不是 0。因为速度不能为 0如果初始左边界取 0在计算 can_finish(0) 或者 mid 为 0 时会发生除零错误。取 1 不仅语义正确也避免了额外的异常判断。4. 实战中踩过的坑常见问题与排查4.1 为什么是 hours h 而不是 hours h每次讲这道题几乎都有人问判断条件为什么写成 hours h因为题目要求“在 h 小时内吃完”意思是时间不超过 h 都可以。等于 h 当然是可行的狒狒刚好在警卫回来前吃完没有任何问题。所以判断条件必须是 。如果你写成 就会漏掉恰好等于 h 的情况导致最终答案偏大。我建议在复盘时把这个判断条件和“至少需要多少小时”这个概念绑定。can_finish(speed) 表达的意思是速度等于 speed 时最少需要 hours 小时只要 hours 不超过给定的 h就认为这个速度可行。边界情况的敏感性是二分题最容易丢分的地方尤其是这种“等于是否合法”的判断一定要回到题意本身去确认。4.2 上界的正确取法与理论分析上界取 max(piles) 而不是 sum(piles)这一点也值得展开。从理论上看速度取 max(piles) 时每个堆都能在1小时内吃完总耗时正好是 N 小时。如果题目给的 h 小于 N那么这道题其实无解但 LeetCode 的测试数据保证了 h N所以不存在这种情况。如果上界取 sum(piles)虽然也能通过因为二分搜索依然能在更大的范围内找到正确答案但搜索范围变大循环次数会增加整体效率会略微降低。看一下两组极端数据piles [1000000000, 1000000000, 1000000000]max 是 10^9sum 是 3 × 10^9二分查找的次数差距大约是 log2(3) ≈ 1.58 次影响不大。但如果堆数非常多比如 10^5 堆sum 会比 max 大 10^5 倍二分次数差距就会明显拉开。所以养成习惯优先采用最贴近答案边界的上下界而不是无脑取一个很大的数。4.3 语言类型与整型溢出的隐蔽坑Python 的 int 是任意精度所以我在本地测试时完全感受不到溢出的问题。但如果你用 C 或 Java 提交hours 的累加可能会超出 int 的范围。比如 piles 的长度是 10^4每堆是 10^9速度很小时hours 累加后可能达到 10^13 级别明显超过 int 的约 2.1 × 10^9 上限。所以用 C 时hours 要声明为 long long用 Java 时要用 long 类型。这个坑特别隐蔽因为本地小数据测试跑不出问题一提交就报错或者答案错误。我的习惯是写完代码先看一眼变量类型凡是可能累加大数的变量一律直接上 64 位整型。这不是小题大做而是刷题中非常实用的防错策略。4.4 常见问题速查表问题现象可能原因解决方案提交超时使用暴力递增枚举速度改用二分答案复杂度降为 O(N log maxP)答案比预期大判断条件写成 hours h改为 hours h答案比预期小hours 计算时向下取整用 (p speed - 1) // speed除零异常左边界初始化为 0左边界从 1 开始C/Java 提交答案错误int 溢出导致 hours 不准hours 用 long long 或 long5. 刷题方法论热题100的正确打开方式5.1 一题三吃从这道题延伸到同类题热题100的价值不在单题而在题目之间的横向联系。做完爱吃香蕉的狒狒之后我强烈建议趁热打铁把下面这几道题放在同一天做搜索旋转排序数组33、在排序数组中查找元素的第一个和最后一个位置34、寻找旋转排序数组中的最小值153。这几道题都属于二分查找专题但考察的细节各有侧重33 号题考的是二分查找过程中对有序区间的判断34 号题考的是找左边界的模板变形153 号题考的是无序中找最小值的特殊条件。如果时间允许还可以再往前延伸一步看看“分割数组的最大值”这类题——它同样用二分答案的思想但难点变成了如何判断一个候选答案是否可行。你会发现一旦第一道二分答案题真的吃透了后面这些题的核心逻辑都长得很像区别只在于 can_finish 这个函数的具体实现。这就是我常说的“一题三吃”第一遍正常做第二遍改写法第三遍总结迁移到同类题。5.2 复盘笔记怎么写才有效我刷热题100时有一个固定习惯每道题刷完不管做对做错都在笔记里写三行话。第一行是题目的核心考点比如“二分答案向上取整”第二行是这道题最关键的洞察点比如“速度越大耗时越短满足单调性”第三行是错误记录比如“第一次用向下取整导致答案偏小”。别小看这三行字它比贴一大堆代码更有价值因为代码会在一个月后忘掉但核心考点和错误原因能在下次遇到类似题时帮你快速定位思路。对于那些没能一次 AC 的题我会额外记录“卡住的原因”。比如这道题我第一次卡在 hours 的计算上花了二十分钟才意识到是向下取整的问题。这种记录会让自己的薄弱点逐渐显形比盲目刷新题有效得多。热题100一共100道题如果每道题都留下这样的复盘记录刷完之后你会发现自己对每个考点的薄弱环节都了如指掌。5.3 一个真实的刷题节奏建议最后分享一下我推荐的热题100刷题节奏适合每天能抽出一到两小时的人。把100道题按专题分成约15组每天完成一组预计三周刷完第一遍。第一遍不求快但求每道题都能独立写出正确代码第二遍只刷错题和卡壳题重点解决第一遍留下的薄弱点第三遍可以只刷中等和困难题用来在面试前保持手感。我实际做下来第一遍平均每题要花40到60分钟困难题可能超过两小时。这个节奏看起来慢但三周之后的效果比一个月刷300道新题好得多。因为热题100的价值是锚定核心考点而不是追求题量。把这一百道题真正吃透比刷五百道题然后全忘掉更有意义。站在现在往回看爱吃香蕉的狒狒这道题给我最大的收获不是记住了一个二分模板而是建立起了一种条件反射看到“求最小可行值”和“条件单调”立刻想到二分答案。这种条件反射需要刻意练习才能形成。刷题这件事归根结底是训练自己在各种包装下识别同一类模式的能力。热题100提供了足够好的素材剩下的就是踏踏实实把每一道题都拆解到位。希望这篇关于第073题的拆解能让你在二分查找这个专题上少走一些弯路也祝你刷题顺利。