題目網址: https://leetcode.cn/problems/koko-eating-bananas/

題意: Koko 喜歡吃香蕉。這里有 n 堆香蕉, 第 i 堆中有 piles[i] 根香蕉。警衛已經離開了, 並且將在 h 小時後回來。

Koko 可以決定她吃香蕉的速度 k （單位：根 / 小時）。每個小時, 她將會選擇其中一堆的香蕉, 並從中吃掉 k 根。如果這堆香蕉少於 k 根, 她將吃掉這堆所有的香蕉, 然後這一小時內都不會再吃更多的香蕉。  

Koko 喜歡慢慢吃, 但仍然想在警衛回來前吃掉所有的香蕉。

返回她可以在 h 小時內吃掉所有香蕉的最小速度 k, 其中 k 為整數。

Solution：

想法：利用 Binary Search, 其中 k 的區間為 [1, max(piles)], 因為 Koko 吃掉該堆所有的香蕉後, 這一小時內都不會再吃更多的香蕉, 所以 k 取到 max(piles) 即可。此外, left 不能為 0, 否則 mid 有可能為 0, 這會導致計算 time += ceil(1.0 * pile / mid) 時發生錯誤

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1, right = *max_element(piles.begin(), piles.end());

        while (left <= right) {
            int mid = left + (right - left) / 2; // speed

            long cost = 0; // 加總有可能會 overflow, 故取 long
            for (const auto & pile : piles) {
                cost += ceil(1.0 * pile / mid); // 先轉成 float 再運算, 最後取 ceiling
            }

            if (cost <= h) { // 速度過快, 往左區間繼續搜尋
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
  • time：$O(n \cdot log(m))$ ➔ 其中 n 為 piles 的長度, m 為 piles 中的最大值
    • $O(log(m))$ : Binary Search 的次數
    • $O(n \cdot log(m))$ : 每一次 Binary Search 皆須 $O(n)$, 因為計算出 mid 後, 皆須遍歷 piles
  • space：$O(1)$ ➔ 只需常數空間