🍌 爱吃香蕉的珂珂

📝 题目描述

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

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

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

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

📋 代码模版

java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {

    }
}

typescript

function minEatingSpeed(piles: number[], h: number): number {
    
}

💡 提示

1. $1\le piles.length\le {10}^4$
2. $piles.length\le h\le {10}^9$
3. $1\le piles[i]\le {10}^9$

🚀 示例

🖊️ 题解

​ 设 $k$ 为珂珂吃香蕉的速度，随着 $k$ 不断增大，珂珂吃掉每一堆 $piles[i]$ 中的香蕉所花费的时间 $\lceil \frac{piles[i]}{k}\rceil$单调递减，吃掉所有香蕉所花费的时间 $totalH$ 也单调递减，其中 $totalH$ 的计算公式如下。

$$totalH=\sum _{i=0}^{n-1}\lceil \frac{piles[i]}{k}\rceil ,n=piles.length$$

​ 根据上述单调性，我们可以使用二分查找算法，找出满足条件 $totalH\le h$ 的最小速度 $answer$。因为只要得到 $answer$​​，以下两个条件都是必然成立的。

$$\sum _{i=0}^{n-1}\lceil \frac{piles[i]}{low}\rceil >h,low<answer$$$$\sum _{i=0}^{n-1}\lceil \frac{piles[i]}{high}\rceil \le h,high>answer$$

​ 二分查找的下限可以设置为 $1$，这是因为 $1$ 是最小正整数，也是最小速度。而二分查找的上限可以设置为 $piles$ 数组中的最大值 $max$，这是因为题目保证有解，即 $h\ge n$，那么当速度 $k$ 为 $max$ 时，珂珂吃掉每一堆香蕉所花费的时间都为 $1$ 小时，吃掉所有香蕉所花费的时间 $totalH$ 为 $n$ 小时，这确保我们不会遗漏最优解。

​ 综上所述，在区间 $[1,max]$ 中，使用二分查找，得到第一个使得条件 $totalH\le h$ 成立的元素，即为最小速度 $answer$。其中，$totalH\le h$ 也是二分查找中 $check$​ 函数为真的条件。

​ 为了进一步提高算法效率，我们还可以对 $check$ 函数进行优化，具体做法为：在统计总花费时间 $totalH$ 时，若它的值已经超出了 $k$，可直接中断统计，并返回 $false$。

java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1, high = piles[0];
        for (int pile : piles) {
            high = Math.max(high, pile);
        }
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (check(piles, h, mid)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private boolean check(int[] piles, int h, int k) {
        int totalH = 0;
        for (int i = 0; i < piles.length && totalH <= h; i++) {
            totalH += (piles[i] + k - 1) / k;
        }
        return totalH <= h;
    }
}

typescript

function minEatingSpeed(piles: number[], h: number): number {
    const check = (k: number): boolean => {
        let totalH = 0;
        for (let i = 0; i < piles.length && totalH <= h; i++) {
            totalH += Math.ceil(piles[i] / k);
        }
        return totalH <= h;
    }
    let low = 1, high = Math.max(...piles);
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (check(mid)) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

💭 复杂度分析

​ 基于二分查找的解决方案的复杂度分析如下。

• 时间复杂度：$O(n\log M)$。其中 $M$ 为数组中的最大值，$n$ 为数组长度。
• 空间复杂度：$O(1)$。