Intuition#

在答案空間 [1, max(piles)] 上二分搜尋，找到最小的吃速 k 使得總時間不超過 h。

• 吃速越快，需要的時間越少 – 具有單調性
• 不需要在陣列上二分，而是在「答案空間」上二分
• 對每個候選速度 k，計算吃完所有香蕉需要的總時間

Approaches#

1: Linear Search#

• 概念: 從 k=1 開始逐一嘗試，直到找到第一個能在 h 小時內吃完的速度
• 時間複雜度: O(max(piles) * n)
• 空間複雜度: O(1)

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#

• 概念: 在 [1, max(piles)] 的答案空間上二分搜尋最小可行的 k
• 時間複雜度: O(n * log(max(piles)))
• 空間複雜度: 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
    }
}

計算總時間時要用 Long 避免溢位。向上取整的技巧：(p + k - 1) / k 等同於 ceil(p / k)。

🔑 Takeaways#

• Pattern: 在答案空間上二分搜尋（Binary Search on Answer）
• 關鍵技巧: 當問題是「找最小的 x 使得條件成立」且條件具有單調性時，就可以在答案空間上二分。這是一個非常通用的模式