爱吃香蕉的狒狒

难度: 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

提示：

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

注意：本题与主站 875 题相同： https://leetcode-cn.com/problems/koko-eating-bananas/

Submission

运行时间: 43 ms

内存: 17.1 MB

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        def check(k):
            hours = 0
            for num in piles:
                hours += ceil(num / k)
            return hours <= h

        left, right = max(1, sum(piles) // h), max(piles)
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

Explain

这个问题的核心是使用二分搜索来确定狒狒吃完所有香蕉的最小速度K。首先，定义一个辅助函数check(k)，该函数用于验证以速度k是否可以在H小时内吃完所有香蕉。对于每堆香蕉，计算狒狒以速度k吃完它所需的小时数（向上取整），并累加所有堆所需的总小时数。如果总小时数小于等于H，返回真，否则返回假。然后，使用二分搜索在可能的速度范围内查找最小的K。速度的初始范围设置为从1到最大堆的香蕉数。二分搜索的逻辑是：如果中间速度mid可以在H小时内吃完所有香蕉，则尝试更小的速度区间；否则，尝试更大的速度区间。当左右边界相遇时，找到了最小的速度K。

时间复杂度: O(N log M)

空间复杂度: O(1)

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def check(k):  # 检查以速度k是否能在h小时内吃完所有香蕉
            hours = 0
            for num in piles:  # 遍历每一堆香蕉
                hours += ceil(num / k)  # 计算吃完这堆香蕉所需的小时数，并向上取整
            return hours <= h  # 如果总小时数不超过h，则返回True

        left, right = max(1, sum(piles) // h), max(piles)  # 确定二分搜索的初始边界
        while left < right:  # 当左边界小于右边界时
            mid = left + (right - left) // 2  # 计算中值
            if check(mid):  # 如果以mid速度可行
                right = mid  # 尝试更小的速度
            else:
                left = mid + 1  # 尝试更大的速度
        return left  # 返回找到的最小速度K

Explore

在确定吃香蕉的最小速度时，我们希望确保速度的下限是合理的。如果将速度设为0或太低，则不可能在限定时间内吃完所有香蕉。表达式`sum(piles) // h`计算了平均每小时至少需要吃的香蕉数，以保证在`h`小时内能吃完所有香蕉。使用`max(1, sum(piles) // h)`是为了确保速度不低于1（因为速度不能为0），同时考虑到如果`sum(piles) // h`结果为0（当`sum(piles) < h`时），至少保证速度为1。这样的设置保证了速度的下限是实际情况下可能的最小速度，既实用又高效。

在确定狒狒吃香蕉的速度上限时，理论上狒狒每小时吃掉香蕉的最大速度不会超过最大堆中的香蕉数量，即`max(piles)`。这是因为即使速度设定得更高，狒狒也只能在一小时内吃掉一堆中的所有香蕉，而其余时间会空闲。因此，将右边界设置为`max(piles)`是合理的，它足以涵盖所有可能的情况而无需设置更高的值，这避免了不必要的计算，提高了算法效率。

使用`ceil(num / k)`的原因是，这样可以正确处理每堆香蕉不是速度`k`的整数倍的情况。如果直接使用`num / k`，它会产生一个浮点数，可能会在不应该向下取整的场合向下取整，从而导致计算出的总时间少于实际需要的时间。例如，如果一堆有10根香蕉，速度是3根/小时，用`num / k`计算得3.33小时，但实际上需要4小时来吃完这堆香蕉（因为第四小时仍需吃香蕉）。因此，使用`ceil`确保任何有剩余的香蕉都会计入额外的一小时，这样可以保证时间计算的准确性。