875. 爱吃香蕉的珂珂
题目描述
有 n 堆香蕉，第 i 堆有 piles[i] 根。警卫 h 小时后回来。
珂珂选定一个整数速度 k（根/小时）。每个小时她挑一堆吃掉其中 k 根；如果这堆不足 k 根，就把这堆吃完，这一小时剩下的时间不再吃别的堆。
返回能让她在 h 小时内吃完所有香蕉的最小 k。
示例 1
输入：piles = [3,6,7,11], h = 8 输出：4
解释：速度为 4 时各堆分别用 1、2、2、3 小时，共 8 小时。
示例 2
输入：piles = [30,11,23,4,20], h = 5 输出：30
解释：只有 5 小时且有 5 堆，每堆只能用 1 小时，速度至少为最大堆 30。
示例 3
输入：piles = [30,11,23,4,20], h = 6 输出：23
解释：速度为 23 时 30 那堆用 2 小时，其余各 1 小时，共 6 小时。
数据范围
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9
解题思路
速度 k 越大，耗时 Σ⌈p/k⌉ 越小，答案具有单调性，可以在答案空间 [1, max(piles)] 上二分。若速度 mid 来得及（耗时 ≤ h），答案 ≤ mid，hi = mid；否则太慢，lo = mid + 1。
为什么正确
最小可行速度始终在 [lo, hi] 中；hi 总是可行的。
复杂度分析
时间 O(n log M)，M = max(piles)；空间 O(1)。
易错点
向上取整写成 (p + k - 1) // k；C++/Java 中耗时总和可能超过 int，要用 long。下界是 1 而不是 0，否则会除以 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public int minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = 0; for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long hours = 0; for (int p : piles) hours += (p + (long) mid - 1) / mid;
if (hours <= h) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long long hours = 0; for (int p : piles) hours += (p + (long long)mid - 1) / mid;
if (hours <= h) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};func minEatingSpeed(piles []int, h int) int {
lo, hi := 1, 0
for _, p := range piles { if p > hi { hi = p } }
for lo < hi {
mid := (lo + hi) / 2
hours := 0; for _, p := range piles { hours += (p + mid - 1) / mid }
if hours <= h {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var minEatingSpeed = function(piles, h) {
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let hours = 0; for (const p of piles) hours += Math.ceil(p / mid);
if (hours <= h) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};function minEatingSpeed(piles: number[], h: number): number {
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let hours = 0; for (const p of piles) hours += Math.ceil(p / mid);
if (hours <= h) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}