875. 愛吃香蕉的 Koko

思路

這個題目要求一個速度最小值 $x$ ，代表每個小時可以吃多少香蕉，讓 koko 能在限制時間內吃掉所有香蕉。

• 如果 $x$ 很大，根據題目的資料限制，koko肯定能在限制 $h$ 小時當中吃完所有香蕉。
• 如果 $x$ 很小，吃一輩子都吃不完。

面對這樣的題目，很難一次就算出精確的 $x$ ，但是我們知道吃的速度越快，花的時間就越少，也就是說，速度跟消耗的時間成反比。
如果在速度 $x$ 可以吃完，那麼所有 $\geq{x}$ 的速度也一定能吃完，答案的分佈呈現 $[0,0,0,1,1,1]$ 的規律。
因此，現在只要有一個函數用來計算速度為 $x$ 時能否在時間內吃完香蕉，然後利用二分答案的方式，就能逼近速度最小值。

程式碼

1. 開區間二分

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 0, right = ranges::max(piles) + 1;

        auto check = [&](int mid) -> bool {
            if(mid == 0) return false;
            long long time = 0;
            for(int x : piles) {
                time += (x + mid - 1) / mid; // 向上取整
            }
            return time <= h; // 有在限制時間內吃完
        };

        while(left + 1 < right) { // 開區間二分
            int mid = left + (right - left) / 2;
            // 如果速度為 mid 能吃完，那麼速度 > mid 也一定都吃得完，速度最小值在 mid 左邊
            // 反之則速度 < mid 也一定吃不完，速度最小在 mid 右邊
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};

2. 閉區間二分

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1, right = ranges::max(piles);

        auto check = [&](int mid) -> bool {
            if(mid == 0) return false;
            long long time = 0;
            for(int x : piles) {
                time += (x + mid - 1) / mid;
            }
            return time <= h;
        };
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(check(mid)) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(1)$