LeetCode 875. 爱吃香蕉的珂珂

约 5 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 LeetCode 75 字节 华为 B站 虾皮
标签
数组 二分查找

题目描述

✅ 875. 爱吃香蕉的珂珂

image-20260928223331872

image-20260928223331873

题意分析

选定一个正整数速度后，每小时只能吃一堆香蕉；即使提前吃完这一堆，本小时也不能继续吃另一堆。求能在 h 小时内吃完所有香蕉的最小速度，题目保证 h 不少于堆数。

解法：二分最小可行速度

核心思路

[!blue]

先考虑如何判断一个速度 k 是否可行。大小为 pile 的一堆需要 ceil(pile / k) 小时，也就是整数除法 (pile + k - 1) / k。每堆最后不足一小时的部分仍独占一个小时，所以必须逐堆向上取整再求和，不能先合并香蕉总数。总耗时不超过 h，这个速度就可行；吃堆的先后顺序不影响该总和。

随着 k 增大，每堆耗时只会减少或不变，总耗时也不会增加。因此速度范围分成“不可行的一段”和“可行的一段”，目标就是找到第一个可行速度，无需逐个尝试。

令 M 为最大堆大小，答案一定在 [1, M] 内：速度至少为一；速度达到 M 时每堆都只需要一小时，而题目保证 h >= piles.length，所以右端一定可行。

二分始终保留包含最小答案的闭区间 [left, right]。若 mid 可行，答案不超过它，令 right = mid，保留中点继续找更小速度；若 mid 不可行，那么所有不超过它的速度也不可行，令 left = mid + 1。只要 left < right，中点就小于右端，两种更新都会缩小区间；边界相等时，剩下的就是最小可行速度。

判定中使用 long 或 int64 计算耗时，并在除法前提升类型。累计值一旦超过 h 就返回失败，因为后面的堆只会继续增加耗时。

解题步骤

  1. 扫描数组得到最大堆大小，初始化 left = 1、right = M。
  2. 在 left < right 时计算 mid = left + (right - left) / 2。
  3. 逐堆累计向上取整后的小时数，判断速度 mid 能否在 h 小时内完成。
  4. 可行就令 right = mid，不可行就令 left = mid + 1。
  5. 当两端重合时返回 left。若速度一已经可行，搜索自然收缩到一；若每堆只能分到一小时，搜索自然收缩到最大堆大小。

代码实现

class Solution {
    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;

            // 可行速度仍可能就是最小答案，收缩时保留中点。
            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canFinish(int[] piles, int h, int speed) {
        long hours = 0;

        for (int pile : piles) {
            // 每堆独立向上取整，剩余不足一小时也不能分给另一堆。
            hours += (pile + speed - 1L) / speed;

            if (hours > h) {
                return false;
            }
        }

        return true;
    }
}

func minEatingSpeed(piles []int, h int) int {
    left, right := 1, 0
    for _, pile := range piles {
        if pile > right {
            right = pile
        }
    }

    for left < right {
        mid := left + (right-left)/2
        // 可行速度仍可能就是最小答案，收缩时保留中点。
        if canFinishBananas(piles, h, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canFinishBananas(piles []int, h, speed int) bool {
    var hours int64
    for _, pile := range piles {
        // 每堆独立向上取整，剩余不足一小时也不能分给另一堆。
        hours += (int64(pile) + int64(speed) - 1) / int64(speed)
        if hours > int64(h) {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n \log(M+1))$。n 是堆数，M 是最大堆大小；先扫描数组确定上界，每次二分判定最多扫描 n 堆，速度区间每轮减半。
  • 空间复杂度：$O(1)$。只使用边界、中点和累计时间等变量。

关键点总结

[!green]

  • 每堆分别向上取整，得到固定速度下所需的准确时间。
  • 耗时随速度单调不增，把最优化问题变成寻找第一个可行速度。
  • 更新边界时保留所有可能答案，最后一个候选值就是最小可行速度。

易错点总结

[!yellow]

  • pile / speed 会漏算有余数时的最后一小时；对总香蕉数统一取整又会错误地共享各堆的剩余时间。
  • 左边界不能设为零，否则判定会除零。
  • 中点可行不代表它最小，不能立即返回，也不能用 right = mid - 1 排除它。
  • 当前更新方式配套的是 while (left < right)；改成 left <= right 会在单点区间反复保留同一个中点。

相似题目

题目 难度 关联与区别
1011. 在 D 天内送达包裹的能力 中等 同样二分最小可行能力并计算所需时间，原题是运输容量，本题是吃香蕉速度。
1283. 使结果不超过阈值的最小除数 中等 同样把每项向上取整后的总和作为单调可行性判定。
410. 分割数组的最大值 困难 二分答案并用贪心累计检验是否可行；本题约束耗时并最小化处理速度，该题约束分段数量并最小化最大段和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/67822546
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！