Koko 有
n堆香蕉，第i堆有piles[i]根。守衛會在h小時後回來。Koko 每小時吃速度為k根（每堆吃完才換下一堆，不足 k 根的那堆也算一小時）。求最小的k使得她能在h小時內吃完所有香蕉。
Example:
Input: piles = [3,6,7,11], h = 8 Output: 4
Intuition
TIP
在答案空間 [1, max(piles)] 上二分搜尋，找到最小的吃速 k 使得總時間不超過 h。
- 吃速越快，需要的時間越少 — 具有單調性
- 不需要在陣列上二分，而是在「答案空間」上二分
- 對每個候選速度 k，計算吃完所有香蕉需要的總時間
Approaches
1. Linear Search — O(max(piles) * n) / O(1)
- Idea: 從 k=1 開始逐一嘗試，直到找到第一個能在 h 小時內吃完的速度
- Time:
O(max(piles) * n) - Space:
O(1)
Linear Search Code
class Solution {
fun minEatingSpeed(piles: IntArray, h: Int): Int {
for (k in 1..piles.max()) {
var hours = 0L
for (p in piles) {
hours += (p + k - 1) / k
}
if (hours <= h) return k
}
return piles.max()
}
}⭐ 2. Binary Search on Answer Space — O(n * log(max(piles))) / O(1)
- Idea: 在 [1, max(piles)] 的答案空間上二分搜尋最小可行的 k
- Time:
O(n * log(max(piles))) - Space:
O(1)
class Solution {
fun minEatingSpeed(piles: IntArray, h: Int): Int {
var left = 1
var right = piles.max()
while (left < right) {
val mid = left + (right - left) / 2
var hours = 0L
for (p in piles) {
hours += (p + mid - 1) / mid
}
if (hours <= h) {
right = mid
} else {
left = mid + 1
}
}
return left
}
}WARNING
計算總時間時要用 Long 避免溢位。向上取整的技巧：(p + k - 1) / k 等同於 ceil(p / k)。
🔑 Takeaways
- Pattern: 在答案空間上二分搜尋（Binary Search on Answer）
- Key trick: 當問題是「找最小的 x 使得條件成立」且條件具有單調性時，就可以在答案空間上二分。這是一個非常通用的模式