LeetCode LCR 073. 爱吃香蕉的狒狒

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 073. 爱吃香蕉的狒狒

题意分析

有若干堆香蕉，警卫会在 h 小时后回来。每小时可以挑一堆吃，吃掉至多 k 根；如果这堆不足 k 根，就把这堆吃完，这一小时也不会再去吃别的堆。要求返回能在 h 小时内吃完全部香蕉的最小速度 k。

「吃不满也要占满一小时」这条规则是全部计算的基础。它意味着一堆 p 根香蕉在速度 k 下需要 $\lceil p / k \rceil$ 小时，各堆之间互不共享时间，总耗时就是各堆向上取整之和。

要找的是最小的可行速度。速度越大耗时越短，「速度 k 能否在 h 小时内吃完」这个性质随 k 增大只会从假变真一次——这正是二分答案的信号。题目求的是第一个为真的位置。

约束里堆数可达 $10^4$、单堆香蕉数可达 $10^9$，h 不小于堆数。堆数与单堆数量的量级差异说明：不能对速度做线性试探（值域到 $10^9$），但可以在每次判定里花 $O(n)$ 扫一遍数组，总代价 $O(n \log \max)$ 完全可接受。

边界上要注意：h 至少等于堆数，所以答案一定存在（速度取最大堆时，每堆恰好一小时，总耗时等于堆数，必定不超过 h）；答案至少是 1，至多是最大堆的香蕉数，再大也没有意义。

解法：二分查找判定答案

核心思路

暴力做法是从 k = 1 开始逐个试，每个 k 算一次总耗时，第一个满足 <= h 的就是答案。代价是 $O(n \cdot \max)$，在最大堆达 $10^9$ 时完全不可行。

瓶颈在于线性试探每次只排除一个速度，而「可行性」显然是单调的：若速度 k 能按时吃完，那么任何比 k 大的速度都能（每堆的耗时只会更少或持平）；若 k 不行，任何更小的速度更不行。这个单调性让一次判定就能砍掉一半值域。

于是把速度的取值域 [1, max(piles)] 当作搜索区间。下界取 1 是因为速度必须为正；上界取最大堆，是因为速度再大也不会让任何一堆少于一小时，总耗时已经降到堆数这个下限，继续增大毫无收益。

判定函数是：给定速度 mid，累加每堆的 $\lceil p / mid \rceil$ 得到总耗时，与 h 比较。向上取整用整数写法 (p + mid - 1) / mid，避免浮点误差。

维持的不变量是：答案始终落在 [left, right] 内；left 左侧的所有速度都不可行，right 及其右侧的所有速度都可行。判定为真（可行）时保留 mid（right = mid），因为它自己可能就是最小可行速度；为假时排除（left = mid + 1），因为它和更小的速度都不行。收敛后的 left 就是答案。

解题步骤

先扫一遍求出最大堆的香蕉数作为搜索上界。用最大堆而不是总和，是因为速度超过最大堆之后总耗时不再变化，多出来的值域纯属浪费；上界越紧，二分轮数越少。

令 left = 1、right = max。下界必须是 1 而不是 0，速度为 0 会在判定里除以零。

循环条件写 left < right，收缩到唯一候选时退出。

每轮取 mid = (left + right) >>> 1，然后花 $O(n)$ 遍历所有堆，累加 (pile + mid - 1) / mid 得到总耗时 s。整数向上取整必须这样写，用 Math.ceil(pile * 1.0 / mid) 在大数上会有浮点精度风险。

若 s <= h，速度 mid 可行，答案不会更大，令 right = mid。保留 mid 是因为它有资格当答案，排除就会漏掉最优解。

否则 s > h，mid 太慢，它和所有更小的速度都出局，令 left = mid + 1。

退出时 left == right，返回 left，即最小可行速度。不需要再验证一次，不变量已经保证了它可行且它减一不可行。

以 piles = [3, 6, 7, 11]、h = 8 走一遍：最大堆是 11，搜索区间 [1, 11]。第一轮 mid = 6，耗时为 $\lceil 3/6 \rceil + \lceil 6/6 \rceil + \lceil 7/6 \rceil + \lceil 11/6 \rceil = 1 + 1 + 2 + 2 = 6 \le 8$，可行，right = 6。第二轮 mid = 3，耗时 $1 + 2 + 3 + 4 = 10 > 8$，太慢，left = 4。第三轮 mid = 5，耗时 $1 + 2 + 2 + 3 = 8 \le 8$，恰好卡满，可行，right = 5。第四轮 mid = 4，耗时 $1 + 2 + 2 + 3 = 8 \le 8$，仍然可行，right = 4。此时 left == right == 4，返回 4。验算速度 3 时耗时 10 超限、速度 4 时耗时 8 达标，4 确实是最小可行速度。

代码实现

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int mx = 0;
        for (int pile : piles) {
            mx = Math.max(mx, pile);
        }
        int left = 1, right = mx;
        while (left < right) {
            int mid = (left + right) >>> 1;
            int s = 0;
            for (int pile : piles) {
                s += (pile + mid - 1) / mid;
            }
            if (s <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func minEatingSpeed(piles []int, h int) int {
    left, right := 1, slices.Max(piles)
    for left < right {
        mid := (left + right) >> 1
        s := 0
        for _, pile := range piles {
            s += (pile + mid - 1) / mid
        }
        if s <= h {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

复杂度分析

时间复杂度：$O(n \log M)$，其中 $n$ 是堆数、$M$ 是最大堆的香蕉数。二分把值域从 $M$ 收敛到 1 需要 $O(\log M)$ 轮，每轮的判定要遍历全部堆做一次 $O(n)$ 的累加。

空间复杂度：$O(1)$，除了几个整数变量没有任何额外结构，判定过程原地累加不需要辅助数组。

关键点总结

「求满足条件的最小/最大值」且「条件随参数单调」时，就该想到二分答案。把题目从「直接构造最优解」改写成「反复判定某个候选是否可行」，往往能把难题降成模板题。

二分答案的三个要件要逐一确认：值域的上下界、判定函数、单调性的方向。本题的判定是 $O(n)$ 的贪心累加，单调方向是「速度越大越可行」。

上界要取「使问题平凡可行的最小值」，这里是最大堆而不是总香蕉数。上界越紧，轮数越少，也更容易说服面试官你想清楚了边界。

整数向上取整写成 (a + b - 1) / b，永远不要用浮点除法再取整。大数上的浮点误差会造成极难复现的偶发错误。

判定为真时保留 mid、为假时排除，是「找第一个为真」的固定规则；配合 left < right 与返回 left，整套模板不需要任何循环后的补充判断。

面试视角：先说清「速度与可行性的单调关系」再写代码，这是判卷的核心；很多人直接写二分框架却说不出为什么单调，会被追问到卡住。

面试视角：常见追问是「如果允许一小时内吃多堆呢」。此时总耗时变成 $\lceil \sum p / k \rceil$，单调性依旧但判定式简化，可以直接解析求解不必二分——借这个对比说明「吃不满也占满一小时」这条规则才是本题的难点来源。

易错点总结

错误写法：搜索下界取 0。用例 piles = [3]、h = 1 → 判定时执行 (3 + 0 - 1) / 0，除零异常。速度必须为正整数。

错误写法：搜索上界取所有香蕉之和。用例 piles = [1000000000] * 10000 → 值域从 $10^9$ 膨胀到 $10^{13}$，二分轮数增加且 int 存不下，需换 long，纯属自找麻烦；速度超过最大堆后耗时不再下降。

错误写法：向上取整写成 pile / mid 忘了进位。用例 piles = [3, 6, 7, 11]、h = 8 → 耗时被算成 $0+1+1+1=3$，误判速度 6 甚至更小的速度可行，返回值偏小。

错误写法：向上取整用 (int) Math.ceil(pile * 1.0 / mid)。用例 piles = [1000000000]、mid = 1 → 大数转 double 存在精度损失，个别数据上取整结果偏差 1 小时，导致边界速度被误判。

错误写法：可行时写 right = mid - 1。用例 piles = [3, 6, 7, 11]、h = 8 → 正确答案 4 在某轮成为 mid 后被排除，最终返回 5。

错误写法：不可行时写 left = mid。用例 piles = [3]、h = 1 → 两元素区间里 mid 恒等于 left，区间不收缩，死循环。

错误写法：判定条件写成 s < h。用例 piles = [3, 6, 7, 11]、h = 8 → 耗时恰好等于 8 的速度 4 被判为不可行，返回 5，正确答案是 4；题目是「在 h 小时内」，含等号。

错误写法：把总耗时累加进 int 而不考虑规模。用例 piles 有 $10^4$ 堆、每堆 $10^9$ 根、mid = 1 → 总耗时达 $10^{13}$，int 溢出成负数被误判为可行，返回 1。可以在累加中途一旦超过 h 就提前返回，既防溢出又剪枝。

错误写法：认为答案就是「总香蕉数除以 h 向上取整」。用例 piles = [3, 6, 7, 11]、h = 8 → 总数 27 除以 8 上取整得 4，凑巧正确；但 piles = [30, 11, 23, 4, 20]、h = 6 时该式给出 15，正确答案是 23，因为不能跨堆吃。

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	与本题同题，是二分答案配合 $O(n)$ 判定的标准样板
1011. 在 D 天内送达包裹的能力	中等	判定改为按顺序贪心分段，下界必须取单件最大值否则无解
410. 分割数组的最大值	困难	最小化最大段和，判定同为贪心计数，也可用区间 DP 对照
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定需统计连续可用段，且要先判断整体是否有解
1552. 两球之间的磁力	中等	最大化最小间距，单调方向与本题相反，收缩规则要整体镜像
1231. 分享巧克力	困难	同为最大化最小值，判定是贪心累加分块并统计块数
69. x 的平方根	简单	判定退化成一次乘除，可用来对照左右边界两套取整与收缩的配对