Leetcode 系列 —— 《875. 爱吃香蕉的珂珂》

题目链接

leetcode-cn.com/problems/ko…

解题思路

主要的解题思想是先找出速度的边界条件，速度在可以吃完的前提的下，只能是 0 ~ 最大堆的香蕉数量，
在找到边界条件之后再用二分查找法去找到尽可能最小的速度

// 传入全部的堆，还有最大的小时数，然后一个吃香蕉的速度，用以判断在这个速度下，吃完所有的堆，需要花多久时间
// 假如大于最大的时间，那么就为 false，假如小于或者等于，那么就返回 true
const canEatAll = (piles, h, speed) => {
    let maxTime = 0;

    for (let i = 0; i < piles.length; i++) {
            maxTime += Math.ceil(piles[i] / speed);
    }
    return maxTime <= h;
}

var minEatingSpeed = function (piles, h) {
    // 边界条件，因为每个小时只能吃一个堆，所以假如堆数都大于最大时间了，那么肯定为 false
    if (piles.length > h) return false;
    let max = Math.max(...piles);
    // 假如堆数等于最大时间，那么就代表说，必须一个小时吃一个堆，那么速度就必须是堆里面最大那个
    if (piles.length === h) return max;
    // 主要边界条件，速度尽可能是 0 ~ max，所以得出区间，那么要找最小那个速度，就可以使用二分法去查找
    let min = 0;
    let ret = max;
    while (min <= max) {
        // 取中间那个速度
        let middle = Math.floor((max + min) / 2);
        const isCanEatAll = canEatAll(piles, h, middle)
        if (isCanEatAll) {
            // 假如可以吃完，看速度是否大于之前存储的速度，大于就代表 middle 的指针需要左移
            if (middle > ret) {
                max = middle - 1;
            } else {
                // 假如小于，那么就继续左移看还有没有更小的
                max = middle - 1;
                ret = middle;
            }
        } else {
            // 假如吃不完，那么答案就只能是在右边了，所以指针右移
            min = middle + 1;
        }
    }
    return ret;
};
复制代码