LeetCode875、爱吃香蕉的珂珂

题目描述

珂珂喜欢吃香蕉。这里有 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)

题目解析

题目在说什么

想象一下，你有一只叫珂珂的宠物猴子，它特别爱吃香蕉。现在地上有好多堆香蕉，每堆的数量不一样，比如第一堆有3根，第二堆有6根，第三堆有7根，第四堆有11根。这些数字就是题目里说的 piles 数组。

珂珂有个习惯：它每小时只能吃一堆香蕉，而且吃的时候速度是固定的，比如每小时吃4根。如果它选的那堆香蕉有6根，它先吃掉4根，剩下2根，但这一小时就结束了，它不能继续吃剩下的2根，得等到下一个小时再吃。如果它选的那堆只有3根，它一口气吃完，然后这一小时剩下的时间它就休息了，不再吃别的堆。

现在，警卫走了，h小时后回来。珂珂必须在警卫回来前把所有香蕉都吃完。它想吃得慢一点（速度k小一点），但又要保证能在h小时内吃完。我们要帮它找到那个最小的速度k，既能吃完，又尽量慢。

思路是怎么来的

这个问题看起来有点复杂，但我们可以换个角度想：速度k和吃完需要的时间有什么关系？

如果珂珂吃得很慢，比如每小时只吃1根，那它需要的时间就很长，可能超过h小时。如果它吃得飞快，比如每小时吃100根，那它很快就能吃完，但这样太累了，不符合它“慢慢吃”的愿望。

所以，我们要找一个临界点：速度再小一点就来不及，速度再大一点就太快了。这个临界点就是我们要找的最小速度k。

怎么找这个临界点呢？一个笨办法是从速度1开始试，1不行就试2，2不行就试3……一直试到能吃完为止。但这样太慢了，因为速度可能很大（比如100万）。我们需要一个更聪明的方法。

聪明的方法叫二分查找。想象你在猜一个1到100之间的数字，别人告诉你猜大了还是猜小了。你第一次猜50，如果他说大了，你就知道答案在1到49之间；如果他说小了，答案就在51到100之间。这样每次都能排除一半的可能性，很快就能找到答案。

在这个问题里，速度的范围是从1到最大堆的香蕉数（因为速度再大也没意义，就算每小时吃1000根，一堆最多也就那么多根）。我们用二分查找，每次猜一个速度mid，然后算一下以这个速度吃完需要多少小时。如果时间小于等于h，说明这个速度可行，但可能还可以更小，所以我们在左半边继续找；如果时间大于h，说明速度太小了，需要往大的方向找。

这样反复缩小范围，最后就能找到最小的可行速度。

代码逐步拆解

我们来看参考代码，它分两部分：

第一部分：计算以速度k吃完需要多少小时

private int calHourUsed(int[] piles, int k) {
    int hourUsed = 0;
    for (int p : piles) {
        hourUsed += Math.ceil((double) p / k);
    }
    return hourUsed;
}

这个函数的作用很简单：对于每一堆香蕉（数量是p），计算以速度k吃完这堆需要多少小时。注意，如果p比k小，比如p=3，k=4，那一小时就能吃完，所以需要的时间是1小时，而不是0.75小时。这就是为什么我们要用 Math.ceil（向上取整）：(double) p / k 得到一个小数，比如3/4=0.75，向上取整就是1。把所有堆的时间加起来，就是总时间。

第二部分：二分查找最小速度

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = Arrays.stream(piles).max().getAsInt() + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (calHourUsed(piles, mid) <= h) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

我们一步步拆解：

1. 初始化范围：left = 1（最小速度），right = 最大堆的香蕉数 + 1。为什么加1？因为我们要用左闭右开的区间，即速度范围是[1, max+1)。这样写可以避免一些边界问题，比如当最大速度刚好可行时，我们也能正确地找到它。

2. 循环条件：while (left < right)，只要左边界小于右边界，就继续找。

3. 计算中间值：mid = left + (right - left) / 2。这是二分查找的标准写法，防止left+right太大导致整数溢出。