跳到主要内容

LeetCode 875. 爱吃香蕉的珂珂

本节目标

把吃香蕉的速度作为候选答案，用所需小时数的单调性寻找最小可行速度。

这道题是二分答案解题框架的第一道母题。关键不是模拟每个小时，而是固定一个速度，快速判断能否在时限内吃完。

查看原题

题意与约束​

有若干堆香蕉，第 i 堆有 piles[i] 根。珂珂每小时选择一堆，最多吃 k 根；如果该堆少于 k 根，就吃完这一堆，这个小时不会转去另一堆。求在 h 小时内吃完全部香蕉的最小整数速度 k。

速度为 k 时，吃完一堆 pile 需要：

ceil(pile / k)

小时。各堆互不混合，所以总时间是每堆所需小时数之和。

朴素思路与瓶颈​

从速度 1 开始逐个尝试到最大堆大小 M，每个速度都扫描全部 n 堆，最坏需要 O(nM)。速度越大，所需小时数不会增加，因此可以在速度范围中二分第一个可行值。

从最优化改写为可行性判断​

直接猜最小速度不好处理，但固定速度 speed 后，答案很容易验证：

requiredHours(speed)
    = Σ ceil(pile / speed)

canFinish(speed)
    = requiredHours(speed) <= h

整数除法不能直接得到向上取整。对正整数，可以安全地写成：

(pile + speed - 1) // speed

这样无需浮点数，也不会受到浮点精度影响。C++ 在加法前把 pile 提升为 long long，累计小时数也使用 long long。

为什么具有单调性​

当速度增加时，每一堆所需的小时数都不会增加，因此总小时数也不会增加。于是：

低速：不可行，不可行，……
边界：第一个可行速度
高速：可行，可行，……

可行速度右侧的所有更大速度都可行。我们要找的正是 canFinish(speed) 第一次变为真的位置。

答案上下界​

  • 下界是 1：速度必须是正整数。
  • 上界是最大堆的大小：以该速度吃任何一堆都只需一小时；题目保证 h 不小于堆数，因此该上界一定可行。

真实答案始终位于 [1, max(piles)]。在这个闭区间内二分第一个可行值即可。

循环不变量与正确性​

循环始终维护：最小可行速度位于 [left, right]。

  • 若 mid 可行，最小可行速度不会大于 mid，但 mid 自己可能就是答案，因此保留 [left, mid]。
  • 若 mid 不可行，根据单调性，小于等于 mid 的速度都不可行，因此保留 [mid + 1, right]。

每轮区间严格缩小。结束时 left == right，区间只剩一个仍可能是答案的值，所以返回 left。

代码实现​

两种语言都让辅助函数只判断给定速度是否可行，不修改 piles。一旦累计时间已经超过 h，立即返回失败，避免无意义的后续计算。

C++17
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1;
        int right = *max_element(piles.begin(), piles.end());

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

private:
    bool canFinish(const vector<int>& piles, int h, int speed) {
        long long requiredHours = 0;
        for (int pile : piles) {
            requiredHours += (static_cast<long long>(pile) + speed - 1) / speed;
            if (requiredHours > h) {
                return false;
            }
        }
        return true;
    }
};

复杂度分析​

设香蕉堆数为 n，最大堆大小为 M。

  • 时间复杂度：O(n log M)。二分进行 O(log M) 轮，每轮扫描所有香蕉堆。
  • 额外空间：O(1)。除固定数量的变量外不使用随输入增长的空间。

边界与易错点​

  • h 大于堆数时，答案仍至少为 1，不能把平均值直接当答案。
  • 单堆香蕉也需要按整数小时向上取整，不能用整除向下截断。
  • pile + speed - 1 和总小时数应使用足够宽的整数类型。
  • mid 可行时应保留它，写成 right = mid，否则可能跳过最小可行速度。
  • 最大堆大小只是保证可行的上界，不代表一定是答案。

模式迁移​

当题目变成“机器至少用多快速度才能按时完成工作”“每辆车至少需要多大容量才能在限定趟数内运完”时，仍可固定速度或容量，计算完成任务所需的时间或次数，再二分第一个可行值。变化的是可行性函数，边界二分结构不变。