875.爱吃香蕉的珂珂

发表于： 分类于：
字数： 1363 阅读：≈ 3分钟

🍌 875.爱吃香蕉的珂珂

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

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

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

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

思路

基本思想

开始第一想法是从速度1开始，每次求出按照这个速度吃掉香蕉需要多少时间，当事件刚好小于等于警卫回来的时间h时就可以得到最终的结果，相当于是一个暴力算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    //将h均匀分给piles中的每个数，然后再确定一个k
    public int minEatingSpeed(int[] piles, int h) {
        int k=1;
        while(true){
            //针对每一个k，看花费多少个小时能吃完
            //当花费的时间小于h时就可以返回
            long time=0;
            for(int i=0;i<piles.length;++i){
                time+=(piles[i]+k-1)/k;
            }
            if(time<=h)
                break;
            ++k;
        }
        return k;
    }
}

这种操作方式大部分情况是可行的，但是一旦香蕉数过多，就会导致超时，主要是因为k的求解是逐步进行的，需要从最小的1逐步增长，这导致了时间过长，于是想到了二分查找的方式

二分查找需要找到k的上界和下界，下界就是吃香蕉的最小速度，也就是1，上界就是一小时最多能吃多少香蕉，由于规定一次只能吃一堆，所以最大速度就看哪一堆香蕉最多，这就是最大速度

找到边界之后，就看是二分查找，计算出按照当前时间需要耗费多少时间能吃完香蕉，当耗费的时间大于警卫回来的时间时，此时说明吃慢了，需要提高速度，也就是目标速度在[mid+1,fast]中，当耗费时间小于等于警卫回来的时间时，说明此时的速度就吃的不慢，目标速度在[slow,mid]中

为什么不是[slow,mid-1]呢，这是因为我们要找到一个刚好吃完的速度，因为这个mid的速度此时吃的不慢，说明可能符合要求，如果将mid丢弃，有可能就丢弃了最终目标

相当于不要丢掉任何一个可能的目标

并且就这样不停地更新区间，最终出现的情况就是区间只剩下两个端点，并且一个端点吃慢了，一个端点吃的速度刚好，当二分查找结束时，区间只剩下唯一的一个值，也就是最终的目标，区间更新的代码为：

1
2
3
4
5

if(time<=h)
    fast=mid;
//吃慢了
else
    slow=mid+1;

执行流程

  1. 确定二分查找的边界
  2. 以二分查找确定速度，从而计算出以当前速度要吃多少个小时
  3. 判断耗费时间与警卫回来时间之间的关系，从而更新区间
  4. 就这样不停的更新，当二分查找结束时，就可以得到结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    //将h均匀分给piles中的每个数，然后再确定一个k
    public int minEatingSpeed(int[] piles, int h) {
        if(piles.length==1) 
            return piles[0]%h==0?piles[0]/h:piles[0]/h+1;
        //吃香蕉的速度不顺序查找，而是二分查找，先找到一个合法的，然后逐步减小
        //找到最大速度(最大堆的香蕉数)和最小速度
        int slow=1,fast=piles[0];
        for(int i=1;i<piles.length;++i){
            fast=fast<piles[i]?piles[i]:fast;
        }
        //二分查找找到一个合法的时间
        long time;
        int mid;
        while(slow<fast){
            mid=(slow+fast)/2;
            time=0;
            for(int i=0;i<piles.length;++i){
                //以当前速度吃掉当前堆香蕉需要几小时
                time+=(piles[i]+mid-1)/mid;
            }
            //找到一个合法的时间,继续减小吃香蕉的速度
            //最终不断减小吃香蕉的速度，总有一天区间只剩下两个值
            //一个吃慢了，一个刚好
            if(time<=h)
                fast=mid;
            //吃慢了
            else
                slow=mid+1;
        }
        return fast;
    }
}

总结

主要是从暴力法超时从而想到优化k的更新过程，从逐步更新变成二分查找的方式更新，减小很多无谓的更新步骤，当二分查找结束时，区间中剩下的值就是目标值，需要注意二分查找区间更新时，不要丢掉任何一个可能的目标