LeetCode 875. 爱吃香蕉的珂珂

2026-04-08 HGNULB 约 6 分钟

文章信息 10 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动华为虾皮哔哩哔哩 LeetCode 75

题目描述

✅ 875. 爱吃香蕉的珂珂

题意分析

有 n 堆香蕉，第 i 堆有 piles[i] 根，警卫 h 小时后回来。珂珂选定一个整数速度 k，每小时挑一堆吃，最多吃掉 k 根；如果这堆不足 k 根，她也只吃完这堆就停，剩下的时间这一小时不再吃别的堆。要求在 h 小时内吃完所有香蕉的最小 k。

「这一小时吃不满也不能换堆」这句话是整道题的题眼：它意味着每堆是彼此独立结算的，第 i 堆花的时间就是 ceil(piles[i] / k)，总时间是各堆向上取整之后再求和，而不是「总香蕉数除以 k」。

约束里另外两个信号：n <= h，保证至少存在可行解（速度取最大堆时每堆一小时，总共 n 小时不超过 h）；piles[i] 和 h 都可以到 $10^9$ 量级，说明从 1 开始逐个试速度的做法会超时，同时总小时数的累加有溢出风险。

真正要注意的是：这里要二分的不是数组下标，而是在答案本身的取值范围上二分。速度越大，每堆的耗时越少（或持平），总耗时也就越少；速度越小总耗时越多。这条「速度增大、耗时单调不增」的性质，是把搜索空间对半砍的全部依据。

边界包括：只有一堆香蕉时答案是 ceil(pile / h)；h == n 时被迫用最大堆当速度；答案永远不会超过最大堆，因为再快也省不下「每堆至少一小时」；累加耗时可能远超 int 范围。

解法：二分最小可行速度

核心思路

给定速度 k，一堆 pile 需要的时间是向上取整 ceil(pile / k)，总耗时可以在一次遍历中算出。速度越大，总耗时只会减少或不变，因此“能否在 h 小时内吃完”具有单调性。

搜索区间是 [1, max(piles)]：速度不能为 0；取最大堆大小时，每堆最多用一小时，题目保证 h 不小于堆数，所以右端一定可行。问题转化为在一段 false...true 的判定序列中寻找第一个 true。

二分过程中保持不变量：最小可行速度始终位于闭区间 [left, right]。mid 可行时保留它并令 right = mid；不可行时排除它并令 left = mid + 1。区间收敛到一个值时，该值就是答案。

解题步骤

令 left = 1，扫描数组得到 right = max(piles)。

当 left < right 时计算中点 mid。

遍历每堆香蕉，累加 (pile + mid - 1) / mid；累计时间超过 h 时可提前判定失败。

若速度 mid 可行，收缩右边界到 mid；否则令左边界为 mid + 1。

返回最终重合的边界。

例如 piles = [3,6,7,11]、h = 8：速度 3 需要 10 小时，不可行；速度 4 需要 1+2+2+3=8 小时，可行，所以最小速度是 4。

代码实现

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }

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

    private boolean canFinish(int[] piles, int h, int speed) {
        long hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1L) / speed;
            if (hours > h) {
                return false;
            }
        }
        return true;
    }
}

func minEatingSpeed(piles []int, h int) int {
    left, right := 1, 0
    for _, pile := range piles {
        if pile > right {
            right = pile
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canFinishBananas(piles, h, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canFinishBananas(piles []int, h, speed int) bool {
    var hours int64
    for _, pile := range piles {
        hours += (int64(pile) + int64(speed) - 1) / int64(speed)
        if hours > int64(h) {
            return false
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(n \log M)$，其中 n 是堆数，M 是最大堆大小；每轮判定扫描全部堆，速度区间被二分。

空间复杂度：$O(1)$。

关键点总结

二分的对象是答案范围，不是输入数组下标。

可行性随速度单调变化，目标是寻找第一个可行速度。

每堆耗时必须单独向上取整，不能先把香蕉总数相加。

可行时使用 right = mid，因为 mid 本身可能就是最小答案。

累计时间使用 64 位类型，并可在超过 h 时提前返回。

易错点总结

将耗时写成 pile / speed 会漏掉不足一小时的余数。

左边界设为 0 会产生除零错误。

可行时直接返回 mid，会错过更小的可行速度。

while (left <= right) 与 right = mid 混用会在单点区间死循环。

用 32 位整数累加总耗时，极端输入可能溢出并误判。

相似题目

题目	难度	考察点
1011. 在 D 天内送达包裹的能力	中等	二分运力配合顺序装载
1482. 制作 m 束花所需的最少天数	中等	二分天数配合连续段计数
1552. 两球之间的磁力	中等	二分最小间距求最大值
410. 分割数组的最大值	困难	二分子数组和上限
1231. 分享巧克力	困难	二分最小块甜度
774. 最小化去加油站的最大距离	困难	实数域二分与精度控制
644. 子数组最大平均数 II	困难	二分平均值配合前缀和
668. 乘法表中第k小的数	困难	二分取值并统计不超过个数
719. 找出第 K 小的数对距离	困难	二分距离配合双指针计数
878. 第 N 个神奇数字	困难	二分配合容斥与最小公倍数
1201. 丑数 III	中等	二分序号与容斥计数
LCP 12. 小张刷题计划	中等	二分单日耗时上限
69. x 的平方根	简单	在整数上二分开方
LCR 072. x 的平方根	简单	开方二分的边界写法
LCR 073. 爱吃香蕉的狒狒	中等	与本题同源的换皮版本