875. Koko Eating Bananas - Medium

前往題目

思路

1. 利用binary search(不是搜尋piles array，而是最小數與最大數的區間)
2. 最少的可能是每小時1根香蕉，最大就是piles裡面最大的，因為piles.length <= h，所以最大值一定可以在時限內吃完
3. binary search搜尋，每次計算piles能不能只需要每小時mid根香蕉吃完，如果不行，小指針指向mid + 1，如果可以，那大指針就變為mid，繼續搜尋有沒有可能k更小

沒想到不是search piles，而是區間

Code

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1; // Possible minimum is 1
        int r = 0;
        // Maximum is the largest pile
        for (int pile : piles) {
            r = Math.max(r, pile);
        }
        
        // Until converge
        while (l < r) {
            int mid = l + (r - l) / 2;

            // 無法以每小時mid根吃完
            if (eat(piles, mid) > h) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        // l和r相交就一定是解，因為題目一定有解
        return l;
    }

    private int eat(int[] piles, int k) {
        int h = 0;
        for (int pile : piles) {
            // 剛好整除
            if (pile % k == 0) {
                h += pile / k;
            } else { // 非整除要再多一小時把剩下的吃完
                h += pile / k + 1;
            }
        }
        return h;
    }
}