[LeetCode] 875. Koko Eating Bananas

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, 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 integer K such that she can eat all the bananas within H hours.

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

Constraints:
1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

爱吃香蕉的珂珂。

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/koko-eating-bananas
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是二分法，而且这道题属于是在答案上二分的类型。这里题目的限制条件的最后一条规定了 piles[i] 不会大于 10 的九次方，所以二分法的上界我直接就取了 10^9。这里二分是在分猴子吃香蕉的速度，这是最后要求的答案。二分法得到某一个速度 mid 之后，去计算吃掉所有香蕉需要花费的时间。这里我们需要额外写一个函数去做计算时间的工作。在这个计算时间的函数里，对于某一堆香蕉，如果香蕉数 % 速度不等于 0，那么意味着时间需要 + 1。例子，比如吃的速度是 3，但是香蕉有 10 个，那么就必须分 4 个小时吃完。注意因为题目要我们计算的是最小速度，所以如果计算出来的时间小于 H 则说明速度快了，需要往左半边走，减慢速度；反之则往右半边走，加快速度。二分法的 while 循环退出的那一刻，low 就是满足题意的最小速度。同时注意二分法的左指针初始化不能为 0，因为这里是对吃香蕉的速度做二分，如果涉及 0，计算时间的时候是会报错的，除法分母不能为 0。

二刷我把 getHour 函数改成 long 型了，因为官方加了新的 case。整形是过不去的。

复杂度

时间O(mlogn) - logn的部分是在做二分，乘以 m 是因为每得到一个速度之后都要带回 piles 去计算时间
空间O(1)

代码

Java实现一

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int low = 1;
        int high = 1000000000;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long hour = getHour(piles, mid);
            if (hour <= H) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private long getHour(int[] piles, int speed) {
        long res = 0;
        for (int p : piles) {
            res += p / speed;
            if (p % speed != 0) {
                res++;
            }
        }
        return res;
    }
}

Java实现二

我再提供一个左闭右开的二分代码。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1;
        int high = (int) Math.pow(10, 9);
        while (low < high) {
            int mid = low + (high - low) / 2;
            long hour = helper(piles, mid);
            // 如果耗时太多，说明速度太慢，需要移动左指针
            // 反之移动右指针
            if (hour > h) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private long helper(int[] piles, int speed) {
        long res = 0;
        for (int p : piles) {
            res += p / speed;
            if (p % speed != 0) {
                res++;
            }
        }
        return res;
    }
}

[LeetCode] 875. Koko Eating Bananas

思路

复杂度

代码

Java实现一

Java实现二

相关题目