算法学习

Appearance

875. 爱吃香蕉的珂珂 Medium ​

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

解题思路 ​

输入： 一个整数数组 piles 表示香蕉的堆数，每堆的香蕉数量；一个整数 h 表示警卫离开的时间（小时数）

输出： 返回可以在 h 小时内吃完所有香蕉的最小速度 k

本题属于典型的二分答案类问题，其核心在于：在一个具有单调性的答案区间上，二分查找满足条件的最小速度。

步骤详解：

  1. 确定搜索区间：

    • 吃香蕉的最小速度不能为 0，因此左边界 left = 1
    • 最大速度不超过最大堆中的香蕉数 right = max(piles)（一小时吃完最大的一整堆）

  2. 二分搜索：

    • 每次取中间速度 k = (left + right) // 2
    • 用该速度 k 计算吃完所有香蕉所需的总时间：
      • 对于每一堆 p，所需时间为 ceil(p / k)
    • 如果总时间 <= h，说明当前速度可行，尝试找更小的速度（right = k - 1）
    • 否则说明速度太慢，需增大速度（left = k + 1）

  3. 返回结果：

    • 在满足条件的过程中，记录可行的速度 res
    • 最终当二分结束，res 即为可以在 h 小时内吃完香蕉的最小速度

代码实现 ​

python
import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 初始化左右边界：
        # 最小速度不能是 0，所以从 1 开始（题意保证至少吃一根）
        # 最大速度不超过最大的香蕉堆数量（因为一次最多吃一堆）
        left, right = 1, max(piles)

        res = right  # 初始化结果为最大值

        while left <= right:
            # 当前尝试的吃香蕉速度
            k = left + (right - left) // 2

            totalTime = 0  # 计算在该速度下吃完所有香蕉所需的总小时数
            for p in piles:
                # 每堆香蕉都要向上取整计算时间，比如 5 / 2 = 2.5，要算作 3 小时
                totalTime += math.ceil(p / k)

            if totalTime <= h:
                # 当前速度 k 能在 h 小时内吃完，尝试更慢的速度
                res = k
                right = k - 1
            else:
                # 当前速度太慢，吃不完，尝试更快的速度
                left = k + 1

        return res  # 返回满足条件的最小吃香蕉速度
javascript
const minEatingSpeed = function(piles, h) {
    // 初始化搜索区间：最小速度不能是 0，所以从 1 开始
    let left = 1;
    let right = Math.max(...piles); // 最大速度不超过香蕉堆中的最大值

    let res = right; // 初始化结果为最大速度，逐步尝试更小的可行速度

    while (left <= right) {
        // 当前尝试的吃香蕉速度 k
        let k = left + Math.floor((right - left) / 2);

        let totalTime = 0; // 记录以当前速度吃完所有香蕉的总耗时

        // 遍历每一堆香蕉，计算每堆所需时间（向上取整）
        for (let p of piles) {
            totalTime += Math.ceil(p / k);
        }

        if (totalTime <= h) {
            // 当前速度可以在 h 小时内吃完，记录当前速度
            res = k;
            // 尝试更慢的速度，看看是否还能吃完
            right = k - 1;
        } else {
            // 当前速度太慢，吃不完，尝试更快的速度
            left = k + 1;
        }
    }

    return res; // 返回满足条件的最小吃香蕉速度
};

复杂度分析 ​

时间复杂度：O(nlog M), M 为 piles 的长度

空间复杂度：O(1)

链接 ​

875 国际版

875 中文版