875. Koko Eating Bananas

https://leetcode.com/problems/koko-eating-bananas/

Koko loves to eat bananas. There are n piles of bananas, the ith 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 will not eat any more bananas during this hour.

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

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 <= 104

• piles.length <= h <= 109

• 1 <= piles[i] <= 109

Solution:

珂珂每小时最多只能吃一堆香蕉，如果吃不完的话留到下一小时再吃；如果吃完了这一堆还有胃口，也只会等到下一小时才会吃下一堆。

他想在警卫回来之前吃完所有香蕉，让我们确定吃香蕉的最小速度K。函数签名如下：

int minEatingSpeed(int[] piles, int H);

那么，对于这道题，如何运用刚才总结的套路，写出二分搜索解法代码？

按步骤思考即可：

1、确定x, f(x), target分别是什么，并写出函数f的代码。

自变量x是什么呢？回忆之前的函数图像，二分搜索的本质就是在搜索自变量。

所以，题目让求什么，就把什么设为自变量，珂珂吃香蕉的速度就是自变量x。

那么，在x上单调的函数关系f(x)是什么？

显然，吃香蕉的速度越快，吃完所有香蕉堆所需的时间就越少，速度和时间就是一个单调函数关系。

所以，f(x)函数就可以这样定义：

若吃香蕉的速度为x根/小时，则需要f(x)小时吃完所有香蕉。

代码实现如下：

// 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉// f(x) 随着 x 的增加单调递减int f(int[] piles, int x) {    int hours = 0;    for (int i = 0; i < piles.length; i++) {        hours += piles[i] / x;        if (piles[i] % x > 0) {            hours++;        }    }    return hours;}

target就很明显了，吃香蕉的时间限制H自然就是target，是对f(x)返回值的最大约束。

2、找到x的取值范围作为二分搜索的搜索区间，初始化left和right变量。

珂珂吃香蕉的速度最小是多少？多大是多少？

显然，最小速度应该是 1，最大速度是piles数组中元素的最大值，因为每小时最多吃一堆香蕉，胃口再大也白搭嘛。

这里可以有两种选择，要么你用一个 for 循环去遍历piles数组，计算最大值，要么你看题目给的约束，piles中的元素取值范围是多少，然后给right初始化一个取值范围之外的值。

我选择第二种，题目说了1 <= piles[i] <= 10^9，那么我就可以确定二分搜索的区间边界：

public int minEatingSpeed(int[] piles, int H) {    int left = 1;    // 注意，right 是开区间，所以再加一    int right = 1000000000 + 1;    // ...}

3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

现在我们确定了自变量x是吃香蕉的速度，f(x)是单调递减的函数，target就是吃香蕉的时间限制H，题目要我们计算最小速度，也就是x要尽可能小：

Image

这就是搜索左侧边界的二分搜索嘛，不过注意f(x)是单调递减的，不要闭眼睛套框架，需要结合上图进行思考，写出代码：

public int getFinishedHours(int[] piles, int speed)
    {
        int result = 0;
        for(int count: piles)
        {
            result += count/speed;
            if(count%speed > 0)
            {
                result++;
            }
        }
        return result;
    }

PS：关于mid是否需要 + 1 的问题，前文 二分搜索算法详解 进行了详细分析，这里不展开了。

至此，这道题就解决了，现在可以把多余的 if 分支合并一下，最终代码如下：

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        
        int left = 1;
        int right = 1000000000+1;
        while(left + 1 < right)
        {
            int mid = left+(right-left)/2;
            if(getFinishedHours(piles, mid) > h)
            {
                left = mid;
            }
            else 
            {
                right = mid;
            }
        }
        
        if(getFinishedHours(piles, left) <= h) return left;
        if(getFinishedHours(piles, right) <= h) return right;
        return -1;    
    }
    
    public int getFinishedHours(int[] piles, int speed)
    {
        int result = 0;
        for(int count: piles)
        {
            result += count/speed;
            if(count%speed > 0)
            {
                result++;
            }
        }
        return result;
    }
}

PS：我们代码框架中多余的 if 分支主要是帮助理解的，写出正确解法后建议合并多余的分支，可以提高算法运行的效率。