LeetCode 875: Koko Eating Bananas (Binary Search on Answer)
LeetCode 875Binary SearchMonotonicInterviewToday we solve LeetCode 875 - Koko Eating Bananas.
Source: https://leetcode.com/problems/koko-eating-bananas/
English
Problem Summary
You are given piles of bananas and an integer h. Koko chooses an eating speed k bananas/hour, and for each pile she spends ceil(pile / k) hours. Find the minimum integer k such that all piles are finished within h hours.
Key Insight
This is a classic binary search on answer problem. If a speed k is feasible (total hours ≤ h), then any larger speed is also feasible. That monotonicity lets us binary search the first feasible speed.
Brute Force and Limitations
Brute force tries k = 1..max(piles) and computes total hours each time. Complexity is O(n * maxPile), too slow when pile values are large (up to 1e9).
Optimal Algorithm Steps
1) Search range: left = 1, right = max(piles).
2) For a candidate speed mid, compute hours = Σ ceil(pile / mid).
3) If hours ≤ h, speed is feasible; move right bound to mid.
4) Otherwise speed is too slow; move left bound to mid + 1.
5) When left == right, that value is the minimum feasible speed.
Complexity Analysis
Time: O(n log M), where M = max(piles).
Space: O(1) extra space.
Common Pitfalls
- Using floating-point ceil unnecessarily; integer formula is safer: (pile + k - 1) / k.
- Binary search boundary update mistakes causing infinite loops.
- Integer overflow in hour accumulation; use long/long long when needed.
- Returning any feasible k instead of the minimum feasible k.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for (int p : piles) right = Math.max(right, p);
while (left < right) {
int mid = left + (right - left) / 2;
long hours = 0;
for (int p : piles) {
hours += (p + mid - 1L) / mid;
}
if (hours <= h) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}func minEatingSpeed(piles []int, h int) int {
left, right := 1, 0
for _, p := range piles {
if p > right {
right = p
}
}
for left < right {
mid := left + (right-left)/2
hours := int64(0)
for _, p := range piles {
hours += int64((p + mid - 1) / mid)
}
if hours <= int64(h) {
right = mid
} else {
left = mid + 1
}
}
return left
}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;
long long hours = 0;
for (int p : piles) {
hours += (p + mid - 1LL) / mid;
}
if (hours <= h) right = mid;
else left = mid + 1;
}
return left;
}
};from typing import List
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
hours = 0
for p in piles:
hours += (p + mid - 1) // mid
if hours <= h:
right = mid
else:
left = mid + 1
return leftvar minEatingSpeed = function(piles, h) {
let left = 1;
let right = 0;
for (const p of piles) right = Math.max(right, p);
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
let hours = 0;
for (const p of piles) {
hours += Math.floor((p + mid - 1) / mid);
}
if (hours <= h) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};中文
题目概述
给定若干堆香蕉 piles 和总时长 h。Koko 选择速度 k（每小时吃 k 根），每堆需要 ceil(pile / k) 小时。求能在 h 小时内吃完所有香蕉的最小整数速度 k。
核心思路
这是典型的答案二分。如果速度 k 可行（总耗时 ≤ h），那么更大的速度一定也可行，满足单调性，可以二分查找“第一个可行速度”。
暴力解法与不足
暴力法会从 k=1 枚举到 max(piles)，每次都遍历所有堆计算耗时，复杂度 O(n * maxPile)，在最大数据下会超时。
最优算法步骤
1）二分范围设为 [1, max(piles)]。
2）对候选速度 mid 计算总小时数 Σ ceil(pile / mid)。
3）若总小时 ≤ h，说明可行，收缩右边界到 mid。
4）否则速度太慢，左边界移动到 mid + 1。
5）循环结束时 left == right，即最小可行速度。
复杂度分析
时间复杂度：O(n log M)，其中 M=max(piles)。
空间复杂度：O(1)。
常见陷阱
- 直接用浮点 ceil，容易带来精度与性能噪声；推荐整数写法：(pile + k - 1) / k。
- 二分边界更新不严谨导致死循环。
- 累加小时数时整型溢出，应使用长整型。
- 只找到“可行速度”就返回，遗漏“最小可行”的要求。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for (int p : piles) right = Math.max(right, p);
while (left < right) {
int mid = left + (right - left) / 2;
long hours = 0;
for (int p : piles) {
hours += (p + mid - 1L) / mid;
}
if (hours <= h) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}func minEatingSpeed(piles []int, h int) int {
left, right := 1, 0
for _, p := range piles {
if p > right {
right = p
}
}
for left < right {
mid := left + (right-left)/2
hours := int64(0)
for _, p := range piles {
hours += int64((p + mid - 1) / mid)
}
if hours <= int64(h) {
right = mid
} else {
left = mid + 1
}
}
return left
}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;
long long hours = 0;
for (int p : piles) {
hours += (p + mid - 1LL) / mid;
}
if (hours <= h) right = mid;
else left = mid + 1;
}
return left;
}
};from typing import List
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
hours = 0
for p in piles:
hours += (p + mid - 1) // mid
if hours <= h:
right = mid
else:
left = mid + 1
return leftvar minEatingSpeed = function(piles, h) {
let left = 1;
let right = 0;
for (const p of piles) right = Math.max(right, p);
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
let hours = 0;
for (const p of piles) {
hours += Math.floor((p + mid - 1) / mid);
}
if (hours <= h) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
Comments