别再暴力搜索了！用二分答案搞定LeetCode 875“爱吃香蕉的珂珂”，附C++/Python代码

二分答案实战从LeetCode 875“爱吃香蕉的珂珂”掌握算法精髓当你面对在h小时内吃完所有香蕉的最小速度k这样的问题时暴力搜索看似直接但效率低下。这正是二分答案算法大显身手的场景——它能将时间复杂度从O(n)优化到O(log n)。让我们以LeetCode 875题为例深入剖析如何识别、设计和实现二分答案解决方案。1. 问题重述与初步分析珂珂面前有n堆香蕉第i堆有piles[i]根。她可以选择吃香蕉的速度k根/小时目标是在警卫h小时后回来前吃完所有香蕉。每小时她选择一堆吃掉k根不足k则全吃。我们需要找到满足条件的最小整数k。关键观察点当k增大时总耗时减少k减小时总耗时增加——这种单调性是二分答案的基础最小k的范围在1到max(piles)之间因为超过最大堆数量没有意义需要设计一个高效函数来判断给定k是否满足h小时限制2. 暴力搜索的局限性最直观的方法是尝试所有可能的k值def minEatingSpeed_brute(piles, h): max_speed max(piles) for k in range(1, max_speed 1): time 0 for pile in piles: time (pile k - 1) // k # 向上取整 if time h: break if time h: return k return max_speed这种解法的时间复杂度是O(n×m)其中n是堆数m是最大堆的大小。当piles[1e9,1e9,...,1e9]且h2e9时这将导致超时。3. 二分答案的适用条件二分答案法有效的前提是问题满足以下特性单调性问题的解存在明确的单调关系本题中k增大→总时间减少k减小→总时间增加可判定性对于任意候选k可以高效验证是否满足条件有界解空间解存在于一个确定的范围内提示二分答案特别适合最小化最大值或最大化最小值类问题如本题的最小速度k4. 二分答案的实现框架标准的二分答案包含三个核心部分确定搜索范围左边界left最小可能值本题为1右边界right最大可能值本题为max(piles)设计check函数计算给定k时的总耗时判断是否≤h二分搜索逻辑根据check结果调整搜索区间终止条件处理4.1 C实现class Solution { public: bool canEatAll(vectorint piles, int h, int k) { long hours 0; for (int pile : piles) { hours (pile k - 1) / k; // 向上取整 if (hours h) return false; } return true; } int minEatingSpeed(vectorint piles, int h) { int left 1; int right *max_element(piles.begin(), piles.end()); int result right; // 初始化为最大值 while (left right) { int mid left (right - left) / 2; if (canEatAll(piles, h, mid)) { result mid; right mid - 1; // 尝试更小的k } else { left mid 1; // 需要更大的k } } return result; } };4.2 Python实现import math def minEatingSpeed(piles, h): left, right 1, max(piles) result right while left right: mid (left right) // 2 total sum(math.ceil(pile / mid) for pile in piles) if total h: result mid right mid - 1 else: left mid 1 return result5. 关键细节与优化5.1 向上取整的技巧计算每小时吃k根需要的时间时常规写法是time pile // k if pile % k ! 0: time 1更优雅的数学表达是time (pile k - 1) // k5.2 边界条件处理最小k值不能小于1至少每小时吃1根最大k值不必超过最大堆的大小因为再快也不会减少时间h的限制h ≥ piles.length否则无论如何都无法完成5.3 提前终止在check函数中可以实时累加时间并在超过h时立即返回bool canEatAll(vectorint piles, int h, int k) { long hours 0; for (int pile : piles) { hours (pile k - 1) / k; if (hours h) return false; // 提前终止 } return true; }6. 复杂度分析时间复杂度O(n log m)其中n是piles长度m是最大堆大小二分搜索进行O(log m)次迭代每次check需要O(n)时间空间复杂度O(1)只使用了常数额外空间7. 同类问题扩展掌握了二分答案的基本模式后可以解决许多类似问题运输包裹问题LeetCode 1011在D天内运送所有包裹的最小运载能力类似吃香蕉但变成了按顺序装船分割数组的最大值LeetCode 410将数组分成m个连续子数组使最大和最小需要调整check函数计算分段方式最小化去加油站的最大距离LeetCode 774在公路上新增K个加油站使相邻加油站最大距离最小需要处理浮点数二分8. 面试常见考察点面试官可能会从以下角度深入提问如何证明二分答案的正确性为什么选择当前的上界和下界check函数的时间复杂度如何影响整体效率如何处理浮点数精度的二分答案问题如果问题不满足单调性该如何调整在实际编码时我曾遇到一个有趣的情况当piles[1e9]且h1e9时初始right1e9会导致二分次数较多。优化方法是将right初始化为ceil(total/h)其中total是所有香蕉的总数。