875 Koko Eating Bananas

875. Koko Eating Bananas

1. Question

Koko loves to eat bananas. There areN piles of bananas, thei-th pile haspiles[i]bananas. The guards have gone and will come back inHhours.

Koko can decide her bananas-per-hour eating speed ofK. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less thanKbananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integerKsuch that she can eat all the bananas withinHhours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

• 1 <= piles.length <= 10^4

• piles.length <= H <= 10^9

• 1 <= piles[i] <= 10^9

2. Implementation

(1) Binary Search

• 这是最高级的二分查找题目，通过一个函数判断我们是否应该在左区间还是右区间查找。

• 首先题目要求我们找到一个最小的速度，使得能在H个小时内吃完所有piles里的香蕉。我们可以发现最小的速度是1，最大的速度则是piles里最大的pile，确定好范围后我们就可以进行二分查找

• 在二分过程中，我们通过getHours()得知以当前的rate吃完所有pile的香蕉需要多少时间，如果所需时间小于等于 H, 我们可以进一步降低rate, 将maxRate更新为targetRate, 否则所需时间超过H, 我们要提高rate, 将minRate更新为target + 1

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int minRate = 1, maxRate = Integer.MIN_VALUE;

        for (int pile : piles) {
            maxRate = Math.max(maxRate, pile);
        }

        while (minRate + 1 < maxRate) {
            int targetRate = minRate + (maxRate - minRate) / 2;

            int hours = getHours(piles, targetRate);

            if (hours > H) {
                minRate = targetRate + 1;
            }
            else {
                maxRate = targetRate;
            }
        }

        if (getHours(piles, minRate) <= H) {
            return minRate;
        }
        else {
            return maxRate;
        }
    }

    public int getHours(int[] piles, int rate) {
        int hours = 0;

        for (int pile : piles) {
            if (pile <= rate) {
                ++hours;
            }
            else if (pile % rate == 0) {
                hours += pile / rate;
            }
            else {
                hours += pile / rate + 1;
            }
        }
        return hours;
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(nlog(maxRate - 1)), 我们在[1, maxRate]范围内进行二分查找，每找打一个targetRate,都会扫一遍piles数组确认所需要多少时间吃完所有pile的香蕉。 空间复杂度O(1)