难度: 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 <= 104piles.length <= h <= 1091 <= piles[i] <= 109运行时间: 41 ms
内存: 17.1 MB
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
def check(x):
ans = 0
for item in piles:
ans += math.ceil(item / x)
return ans
n, sums, maxs = len(piles), sum(piles), max(piles)
if h == n:
return maxs
l, r = sums // (h + n) + 1, sums // (h - n) + 1
while l <= r:
mid = (l + r) >> 1
if check(mid) <= h:
r = mid - 1
else:
l = mid + 1
return l
此题的解决方法是采用二分查找来找到珂珂可以在 h 小时内吃完所有香蕉的最小速度 k。这里定义了一个 check 函数来判断给定速度 x 下珂珂能否在 h 小时内吃完所有的香蕉。check 函数通过遍历所有香蕉堆，计算在速度 x 下需要的总时间。如果这个总时间小于等于 h，说明这个速度可行。通过不断调整速度的搜索范围（即二分查找的上下界），最终找到可以满足条件的最小速度。二分查找的初始左界 l 和右界 r 的设定基于总香蕉数和堆数的关系，以缩小搜索范围，提高效率。
时间复杂度: O(n log m)
空间复杂度: O(1)
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
def check(x):
# 计算以速度 x 吃完所有香蕉所需的总时间
ans = 0
for item in piles:
ans += math.ceil(item / x)
return ans
n, sums, maxs = len(piles), sum(piles), max(piles)
# 如果每堆香蕉一小时吃一堆的话，最小速度为最大堆的大小
if h == n:
return maxs
# 初始化二分查找的左右界，尝试缩小搜索范围
l, r = sums // (h + n) + 1, sums // (h - n) + 1
while l <= r:
mid = (l + r) >> 1
# 利用 check 函数判断 mid 是否为可行速度
if check(mid) <= h:
r = mid - 1
else:
l = mid + 1
return l
在这个算法中，二分查找的初始上界和下界是基于香蕉总数和时间限制来设定的。下界l为香蕉总数除以时间加上堆数后再加1，目的是确保即使分配最不利，也有足够的速度去吃完所有香蕉。上界r则是香蕉总数除以时间减去堆数后再加1，这是考虑到最快的速度场景。这样做是为了确保搜索范围既包含可能的最小速度，也不过分宽泛以致效率低下。
这里的表达式`sums // (h + n) + 1`和`sums // (h - n) + 1`用于估计可能的最小和最大速度。`sums // (h + n) + 1`作为下界考虑了即使在最慢的情况下也应该有足够的速度完成任务，而`sums // (h - n) + 1`作为上界则考虑到最快情况的可能性。这两个表达式提供了一个合理的速度范围，使得二分查找能更高效地找到解。
如果h的值非常接近n，情况特殊因为每堆香蕉至少需要一小时来处理，这意味着珂珂的吃香蕉速度至少得是每堆中的最大数量。在这种情况下，若h等于n，算法直接返回最大堆的大小作为最小速度，因为没有其他速度可以在每堆只能分配一小时的情况下完成任务。这是一种边界情况，需要特别处理以确保算法的正确性和效率。
是的，退出循环时返回的l总是满足条件的最小速度。在二分查找中，当检测到某个速度mid能让珂珂在规定时间内吃完所有的香蕉时，我们将上界r调整为mid-1，继续寻找是否有更小的可行速度。如果某个速度不可行，就调整下界l为mid+1。最终，当l超过r时，l即为满足条件的最小速度。这是因为最后一次使check函数返回true的mid，其值即为l-1，而l是第一个使check函数返回false的值，因此l是满足条件的最小速度。