华为 OD 训练营 · 题解精讲

LeetCode875、爱吃香蕉的珂珂

LeetCode875、爱吃香蕉的珂珂视频链接：

题目描述

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

题目解析

解题思路

本题要求找到在 h 小时内吃完所有香蕉的最小整数速度 k。核心思路是二分答案：速度 k 越大，所需时间越少；速度 k 越小，所需时间越多。因此可以在速度的可能范围 [1, max(piles)] 内进行二分搜索，找到满足 cal_hour_used(k) <= h 的最小 k。

关键数据结构：二分查找的左右指针 left 和 right。

核心函数 cal_hour_used(piles, k)：计算以速度 k 吃完所有香蕉所需的小时数。对于每堆 p 根香蕉，需要 ceil(p / k) 小时（因为每堆必须吃完才能换下一堆），最后对所有堆求和。

关键步骤

1. 初始化二分区间：left = 1（最小速度），right = max(piles) + 1（开区间右边界，确保覆盖所有可能）。 2. 二分循环：当 left < right 时：

计算中点 mid = (left + right) // 2。
调用 cal_hour_used(piles, mid) 得到所需小时数。
若 <= h，说明当前速度可行，尝试更小速度，令 right = mid。
若 > h，说明速度太小，需要增大，令 left = mid + 1。

3. 返回结果：循环结束时 left == right，即为最小可行速度。

示意图（以 piles=[3,6,7,11], h=8 为例）：


速度范围 [1, 12)
mid=6 → 小时数=1+1+2+2=6 ≤8 → right=6
mid=3 → 小时数=1+2+3+4=10 >8 → left=4
mid=4 → 小时数=1+2+2+3=8 ≤8 → right=4
left=4, right=4 → 返回4

复杂度分析

时间复杂度：O(n log M)，其中 n 为堆数，M = max(piles)。二分查找次数为 O(log M)，每次计算 cal_hour_used 需遍历所有堆 O(n)。
空间复杂度：O(1)，仅使用常数个变量。

参考代码

class Solution:
    # 计算速度k对应的小时数的函数，算出hour_used
    def cal_hour_used(self, piles, k):
        return sum( math.ceil(p/k) for p in piles )

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles) + 1
        while left < right:
            mid = (left + right) // 2
            # 花费时间太少，速度偏大，速度还可以减小，
            # 搜索区间向左折半，right可以向左移动
            if self.cal_hour_used(piles, mid) <= h:
                right = mid
            else:
                left = mid + 1
        return left

← 上一篇

LC860. 柠檬水找零

LC881. 救生艇