526互联

力扣875. 爱吃香蕉的珂珂（二分查找）

发布时间 2023-06-22 16:32:36作者: 翰林猿

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

换句话说，就是找到吃的最慢且能吃完的速度，其实仔细理解一下发现就是 ————— 查找某个函数f（k）中 k 的 最小值 ， 所以我们用最快的二分就好了。

​
class Solution {
    public  int minEatingSpeed(int[] piles, int h) {
        int l = 1;
        int r = Arrays.stream(piles).max().getAsInt();
        int minEatingSpeed = minEatingSpeed(piles, h, l, r);
        return minEatingSpeed;
    }
    public  int minEatingSpeed(int[] piles, int h, int l, int r) {
        //二分查找
        while (l < r) {
            int mid = l + (r - l) / 2;
​
            //以mid作为速度，获取吃的时间，如果发现小于等于指定的时间h，说明以当前mid作为速度可能还是吃的太快了。
            if (eatingTime(piles, mid) <= h) {
                r = mid;
            } else {
                l = mid + 1;    //如果大于指定时间h，说明吃的速度慢了，去数组右边找。
            }
        }
        return l;
    }
​
    public  int eatingTime(int[] piles, int k) {                 
        int eatTime = 0;
        for (int pile : piles) {                                //这里就是所谓的函数f（k）
            eatTime += pile / k + (pile % k > 0 ? 1 : 0);          //用堆除以吃的速度，如果有余，就再+1小时，这样就算出来一堆要吃几个小时
        }
        return eatTime;
    }
​
}