leetcode875. 爱吃香蕉的珂珂(java)-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode875. 爱吃香蕉的珂珂(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

爱吃香蕉的珂珂

难度 - 中等
LC - 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 <= 1E4
piles.length <= h <= 1E9
1 <= piles[i] <= 1E9

leetcode875. 爱吃香蕉的珂珂(java),java,数据结构,算法,java,python,开发语言,算法,数据结构,贪心算法,动态规划

二分查找

由于存在「吃完这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉」的条件，因此不会存在多堆香蕉共用一个小时的情况，即每堆香蕉都是相互独立，同时可以明确每堆香蕉的耗时为 ⌈piles[i]k⌉⌉（其中 k 为速度）。

因此我们可以二分 k 值，在以 k 为分割点的数组上具有「二段性」：

小于 k 的值，总耗时 ans 必然不满足 ans≤h；
大于等于 k 的值，总耗时 ans 必然满足 ans≤h。
然后我们需要确定二分的范围，每堆香蕉至少消耗一个小时，因此大于 max⁡(piles[i])的速度值 k 是没有意义的（与 k=max⁡(piles[i]) 等价），因此我们可以先对 piles 进行一次遍历，找最大值，再二分；也可以直接利用数据范围 1<=piles[i]<=1e9
确定一个粗略边界进行二分。

最后的 getTime函数，只需要计算当前速率 k 所对应的总耗时 ans，再与 h 做比较即可。

代码演示:

 public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        //找出最大一堆的个数 吃香蕉的速度最大就是这个,在大没有意义了
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        while(left < right){
          int mid = left + (right - left) / 2;
          long time = getTime(piles,mid) ;
           if(time <= h){
                right = mid;
            }else if(time > h){
                left = mid + 1;
            }
        }
        return left;
    }

    /**
    * 计算用时
    * speed 吃香蕉的速度
     */
    public long getTime(int[] piles, int speed) {
        long time = 0;
        for (int pile : piles) {
            int curTime = (pile + speed - 1) / speed;
            time += curTime;
        }
        return time;
    }