『LeetCode』875 爱吃香蕉的珂珂

题目

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

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

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23

提示：

\(1 <= piles.length <= 10^{4}\)
\(piles.length <= h <= 10^{9}\)
\(1 <= piles[i] <= 10^{9}\)

相似题目

最小化去加油站的最大距离 (困难)

题解

【爱吃香蕉的珂珂】简单二分

二分查找

按照题目要求，想要直接计算最小速度 \(k\) 是比较困难的，但相反，若是给出速度 \(k\), 想要验证以该速度吃香蕉珂珂能不能在 \(h\) 小时内吃完是很容易的。因此，我们可以使用“猜数字”的方法来获得答案。

但若是按顺序由小到大逐个猜，显然效率太低了，同时注意到：若是速度太慢，那么是吃不完的；而只要速度大于一个临界值，那么就能吃完香蕉，而我们要求的就是这个速度的临界值。显然，该问题具备二段性，通俗的说，我们可以根据速度直接判断我们“猜”的数字在“临界值”的左边还是右边，据此，可以使用二分查找的方法求解。

那么，速度的上界是多少呢？观察提示中的取值范围，从 \(piles.length <= h <= 10^{9}\) 我们可以注意到在 \(h\) 与所给数组 piles 长度相等时结果为数组 piles 中的最大值，而数组中的最大取值为 \(10^{9}\)，所以上界可以取 piles 的最大值或者直接取 \(10^{9}\).

而二分查找的目标，是找到满足“以速度 \(s\) 能在 \(h\) 小时内吃完香蕉”的最小速度。

# Code language: Python
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        def check(s):
            """ 以速度 S 能否在 h 小时内吃完香蕉呢？ """
            cnt = 0
            for p in piles:
                d, m = divmod(p, s)
                cnt += d + (1 if m else 0)
            return cnt <= h

        left, right = 1, max(piles)
        while left < right:
            mid = (left + right) >> 1
            if not check(mid):
                left = mid + 1
            else:
                right = mid
        return left

// Code language: Java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 1;
        for (int p: piles) right = Math.max(right, p);
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(piles, mid) > h) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    public int check(int[] piles, int s) {
        // 最快吃完香蕉的时间
        int cnt = 0;
        for (int p: piles) {
            cnt += p / s + (p % s == 0 ? 0 : 1);
        }
        return cnt;
    }
}

// Code language: Cpp
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1, right = 1;
        for (int p: piles) right = max(right, p);
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(piles, mid) > h) left = mid + 1;
            else right = mid;
        }
        return left;

    }

    int check(vector<int>& piles, int s) {
        // 最快吃完香蕉的时间
        int cnt = 0;
        for (int p: piles) {
            cnt += p / s + (p % s == 0 ? 0 : 1);
        }
        return cnt;
    }
};

时间复杂度: \(O(n \log m)\), \(m, n\) 分别表示数组 piles 中最大值和数组长度
空间复杂度: \(O(1)\)

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』875 爱吃香蕉的珂珂

题目

标签

相似题目

题解

二分查找

最后