LeetCode LCR 073. 爱吃香蕉的狒狒
题目描述
题意分析
每小时只能选择一堆香蕉，最多吃掉
k根；即使这一堆不足k根，吃完后也不能在本小时继续吃另一堆。要求找到能够在h小时内吃完的最小整数速度。因此一堆
p根需要 $\lceil p/k\rceil$ 小时，各堆耗时必须分别向上取整后再相加。题目保证h不小于堆数，所以总能找到可行速度。
解法：二分速度并累计耗时
核心思路
[!blue]
对一个给定速度
k，总耗时可以直接算出：$T(k)=\sum_{p\in piles}\left\lceil\frac{p}{k}\right\rceil$
速度增大时，每堆耗时只会减少或保持不变，所以
T(k)不增。若某个速度已能按时吃完，所有更大速度也可行；若它太慢，所有更小速度都不可行。这就能二分查找第一个满足T(k) <= h的速度。搜索下界为
1，避免零速度。上界取最大堆数量M：此时每堆恰好需要一小时，总耗时为堆数，已经不超过h，所以右端一定可行。速度再大也无法把单堆耗时降到一小时以下。每轮计算中点速度的总耗时
s。若s <= h，中点可能就是最慢可行速度，令right = mid；否则中点及所有更小速度都排除，令left = mid+1。答案始终留在闭区间中，区间收敛后的唯一值就是最小可行速度。正整数除法的向上取整可以写成
(p+mid-1)/mid。代码用 64 位整数累加：堆数最多 $10^4$、单堆最多 $10^9$，速度为一时总耗时可能达到 $10^{13}$，不能按单堆的值域选择累计类型。
解题步骤
- 扫描数组得到最大堆数量，初始化速度范围
[1,M]。- 在左右端不同的情况下取下中点，重新将累计耗时清零。
- 遍历每一堆，累加它在当前速度下所需的完整小时数。
- 能在期限内完成就收右端，否则增大左端；最终返回
left。耗时恰好等于
h也算可行。若h就等于堆数，每堆都只能占一小时，答案是最大堆数量；若所有堆都只有一根，初始搜索范围已经是单点。
代码实现
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int mx = 0;
for (int pile : piles) {
mx = Math.max(mx, pile);
}
int left = 1;
int right = mx;
while (left < right) {
int mid = (left + right) >>> 1;
long s = 0;
for (int pile : piles) {
s += ((long) pile + mid - 1) / mid;
}
if (s <= h) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
import (
"slices"
)
func minEatingSpeed(piles []int, h int) int {
left, right := 1, slices.Max(piles)
for left < right {
mid := (left + right) >> 1
var s int64
for _, pile := range piles {
s += (int64(pile) + int64(mid) - 1) / int64(mid)
}
if s <= int64(h) {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(n\log(M+1))$，其中 $n$ 为堆数、$M$ 为最大堆数量。先线性求上界，每轮判定再线性扫描所有堆。
- 空间复杂度：$O(1)$，只保存速度边界与累计耗时。
关键点总结
[!green]
- 不能跨堆共享一个小时，决定了必须对每堆单独向上取整。
- 总耗时对速度单调不增，二分才能一次排除一整段速度。
- 右端一开始就已证明可行，结束时无需额外验证答案。
易错点总结
[!yellow]
- 把总香蕉数一次除以速度，会错误地把不同堆的剩余时间合并。
- 速度下界取零，会使判定出现除零。
- 将期限内完成写成
s < h，会排除恰好按时完成的最优速度。- 用普通 32 位整数累计全部耗时，可能溢出后误判为可行。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1011. 在 D 天内送达包裹的能力 | 中等 | 同样二分最小可行能力并计算所需时间，原题是运输容量，本题是吃香蕉速度。 |
| 1283. 使结果不超过阈值的最小除数 | 中等 | 同样把每项向上取整后的总和作为单调可行性判定。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！