爱吃香蕉的珂珂

说在前面

🎈每天进行一道算法题目练习，今天的题目是“爱吃香蕉的珂珂”。

问题描述

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

思路分析

首先我们要先理解题目的意思，从题目中提取出有用的信息。阅读完题目后我们可以得到这么几个信息：

• 1、珂珂一个小时内只会吃同一堆香蕉里面的香蕉；
• 2、珂珂可以改变吃香蕉的速度k；
• 3、珂珂需要在h小时内吃完香蕉

题目会给出香蕉的堆数、每一堆的香蕉数目以及h的值，我们需要求出满足条件的k的最小值。

确定二分区间

由于吃香蕉的速度和是否可以在规定时间内吃掉所有香蕉之间存在单调性，因此可以使用二分查找的方法得到最小速度 k。由上面得出的信息1可以知道，珂珂一个小时内只会吃同一堆香蕉里面的香蕉，所以二分区间的最大值为香蕉堆中香蕉数目的最大值high = Math.max(...piles);，提示中有piles[i]所以二分区间的最小值应该为1low = 1;。

缩短区间

每次取区间的中间数为k计算吃完所有香蕉的时间h：

const getTime = (piles, speed) => {
    let time = 0;
    for (const pile of piles) {
        const curTime = Math.floor((pile + speed - 1) / speed);
        time += curTime;
    }
    return time;
};

当前速度吃完所有香蕉的时间比h长则说明速度应该加快，反之则应减慢：

time <= h ? (k = speed,high = speed) : low = speed + 1;

不断缩小区间来锁定答案：

while (low < high) {
    const speed = Math.floor((high + low) / 2);
    const time = getTime(piles, speed);
    time <= h ? (k = speed,high = speed) : low = speed + 1;
}

完整代码如下：

AC代码

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
 var minEatingSpeed = function(piles, h) {
    let low = 1;
    let high = Math.max(...piles);
    let k = high;
    while (low < high) {
        const speed = Math.floor((high + low) / 2);
        const time = getTime(piles, speed);
        time <= h ? (k = speed,high = speed) : low = speed + 1;
    }
    return k;
}

const getTime = (piles, speed) => {
    let time = 0;
    for (const pile of piles) {
        const curTime = Math.floor((pile + speed - 1) / speed);
        time += curTime;
    }
    return time;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。