Koko Eating Bananas

題目描述

給定 piles 陣列（每堆香蕉的數量）和 h 小時。Koko 每小時吃 k 根，吃完一堆才能換下一堆。回傳最小的 k。

輸入：piles = [3,6,7,11], h = 8
輸出：4
解釋：速度 4 → 需要 1+2+2+3 = 8 小時，剛好吃完

解題思路

確定搜尋範圍

最慢 k=1（每小時吃 1 根），最快 k=max(piles)（最大堆一小時吃完）。答案一定在 [1, max(piles)] 之間

二分搜尋速度

mid = (left + right) / 2，嘗試以速度 mid 吃香蕉

計算所需時間

每堆需要 ceil(pile/mid) 小時（整數公式：(pile + mid - 1) / mid），將所有堆的時間加總

判斷可行性

總時間 ≤ h → 可行，right = mid 嘗試更慢的速度；總時間 > h → 不可行，left = mid + 1 加快

回傳最小速度

迴圈結束時 left = right，就是滿足「≤ h 小時吃完」的最小速度

程式碼

C#

csharp

public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int left = 1, right = piles.Max();
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 計算以速度 mid 吃完所有香蕉需要的時間
            long hours = piles.Sum(p => (long)(p + mid - 1) / mid);
            if (hours <= h) {
                right = mid; // 可以更慢
            } else {
                left = mid + 1; // 太慢了，加速
            }
        }
        return left;
    }
}

TypeScript

typescript

function minEatingSpeed(piles: number[], h: number): number {
    let left = 1, right = Math.max(...piles);
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        // 計算所需小時數
        const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
        if (hours <= h) {
            right = mid; // 速度夠快，嘗試更慢
        } else {
            left = mid + 1; // 速度太慢
        }
    }
    return left;
}

Python

python

import math
 
def minEatingSpeed(piles: list[int], h: int) -> int:
    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        # 以速度 mid 吃完所有堆需要的總小時數
        hours = sum(math.ceil(p / mid) for p in piles)
        if hours <= h:
            right = mid  # 可以更慢
        else:
            left = mid + 1  # 太慢了
    return left

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n log m) | O(1) |

其中 n = piles 長度，m = max(piles)。

Time：二分搜尋 O(log m) 輪，每輪遍歷所有堆計算時間 O(n)，合計 O(n log m)
Space：只用了常數個變數，不需要額外空間

圖解

速度範圍 [1, max(piles)]

二分→

嘗試速度 mid

模擬→

計算所需時間

可行→

時間 <= h → 嘗試更慢

收斂→

時間 > h → 加快速度

收斂→

最小可行速度

圖表展示了「Binary Search on Answer」的核心邏輯：答案空間 [1, max(piles)] 具有單調性——速度越快所需時間越少。每次取 mid 模擬吃完所有堆的總時間，根據是否 ≤ h 來決定搜尋方向。

進階觀點

💡面試追問

什麼是 Binary Search on Answer？ 當答案空間有單調性（速度越快 → 時間越少），可以把答案本身當搜尋目標。對每個候選答案驗證可行性，再用二分縮小範圍。類似題：1011（船容量）、410（分割陣列）。
為什麼用整數 ceil 而不是浮點？ ceil(p / mid) 用浮點除法可能有精度問題。改用 (p + mid - 1) / mid 純整數運算更安全。例如 p=7, mid=3 → (7+2)/3 = 3，正確。
溢位風險在哪？ piles.Sum() 每堆最多 10^9，最多 10^4 堆，加總可能到 10^13，超過 int 範圍。C# 中必須用 long 累加。
如果每小時可以吃多堆呢？ 那就變成 1011 題（Capacity To Ship），每「小時」可以連續處理多堆直到超過 k 的容量。

邊界情況

h 等於 piles.length：每堆只有一小時可吃，速度必須是 max(piles) 才能每堆一小時吃完
h 遠大於 piles 總和：速度 1 就足夠，答案為 1
只有一堆香蕉：答案就是 ceil(piles[0] / h)，直接計算即可

理解測驗

🤔 這題的「二分搜尋」搜尋的是什麼？

🤔 為什麼答案空間具有單調性？