Koko Eating Bananas
Koko 有 n 堆香蕉，第 i 堆有 piles[i] 根香蕉，她有 h 小时。她选择一个进食速度 k，也就是每小时吃整数根香蕉，并保持这个速度不变。每小时她从一堆香蕉中吃掉 k 根；如果这堆剩下的香蕉不到 k 根，她就吃完这堆，然后休息到这一小时结束。请返回能让她在 h 小时内吃完所有香蕉的最小 k。
函数
- pilesinteger-array
- 每堆香蕉的数量
- hinteger
- Koko 拥有的小时数
- 返回值integer
- 能在 h 小时内吃完每一堆香蕉的最小整数进食速度，单位为根香蕉每小时
约束条件
1 ≤ piles.length ≤ 50001 ≤ piles[i] ≤ 109piles.length ≤ h ≤ 109，因此答案始终存在。
示例
- 输入
- piles = [4, 10, 7, 3]h = 6
- 输出
- 5
- 解释
- 速度为 5 时，4、10、7 和 3 这些堆分别需要 1、2、2 和 1 小时：总共 6 小时，符合要求。速度为 4 时，它们分别需要 1、3、2 和 1 小时，总共 7 小时。
- 输入
- piles = [30, 11, 23, 4, 20]h = 5
- 输出
- 30
- 解释
- 5 堆和 5 小时意味着每堆恰好有 1 小时，因此速度必须能在 1 小时内清空最大的一堆，也就是 30。在速度为 29 时，那一堆需要 2 小时。
- 输入
- piles = [5, 9, 2]h = 20
- 输出
- 1
- 解释
- 速度为 1 时，这些堆需要 5 + 9 + 2 = 16 小时，远少于 20 小时。速度不可能低于 1，所以答案是 1。
进阶
孪生题：Koko 按顺序吃完整堆香蕉，每天最多吃 k 根，并在 d 天内吃完。最小的 k 是多少？你的搜索需要做哪些改变？
提示
逐个打开提示，每个都会多透露一点。
固定一个速度
k。在这个速度下，吃完一堆p根香蕉需要多少小时？Koko 每小时内不会换堆。吃完所有堆需要多少小时？如果速度
k能及时完成，那么所有更快的速度也都能及时完成。可行的速度会形成一段连续区间，并从答案开始。在从 1 到最大堆的速度范围内进行二分查找。只需遍历一次，就能计算出以中间速度需要的小时数：如果能在
h小时内完成，答案就不大于中间速度；否则，答案就大于中间速度。
题解
答案是速度，不是数组中的位置，而这隐藏着一个二分查找。检查一种速度需要遍历一遍所有堆。如果速度 k 能及时完成，那么所有更快的速度也可以。所以，对从 1 到最大堆大小的速度进行二分查找：大约检查 30 次，而不是最多检查 10 亿次。
从 1 开始，逐个尝试所有速度
结果正确，但无法在最大的测试中运行完毕
思路
Koko 在一小时内不会转去吃另一堆香蕉，因此，一堆 p 根香蕉需要 p / k 小时，向上取整：速度为 4 时，吃 10 根香蕉需要 3 小时。依次尝试速度 1、2、3 等，并返回总时间不超过 h 的第一个速度。它就是最小速度，因为所有更慢的速度都不满足条件；循环会在速度达到最大的一堆香蕉的数量时停止，此时每堆香蕉都只需一小时。
如果 m 是最大的一堆香蕉的数量，那么最多要检查 m 个速度，每个速度检查 n 堆香蕉：对于接近 10^9 的 5000 堆香蕉以及 h = 5000，大约需要 5 × 10^12 步。
算法
- 将
speed = 1。 - 计算以这个速度所需的小时数：对每堆都加上
(pile + speed-1) / speed，并使用 64 位总数。 - 如果总数不超过
h，则返回speed。 - 否则将
speed加 1，然后重新计算。
def minEatingSpeed(piles, h):
speed = 1
while True:
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # a started pile costs a whole hour
if hours <= h:
return speed
speed += 1对速度进行二分查找
思路
随着速度变快，每堆所需的小时数会相同或更少，因此对于“这个速度能否按时完成？”这个问题，答案会从某个位置开始依次是“不能、不能、不能、能”。二分查找可以找到第一个“能”对应的速度。
维护一个始终包含答案的范围 lo 到 hi，初始范围是 1 到最大的一堆，因为以最大一堆的数量作为速度时，每堆只需 1 小时，因此一定能满足要求。如果中间速度 mid 符合要求，答案就是 mid 或更慢的速度，因此设置 hi = mid。如果不符合要求，那么所有更慢的速度也都不符合，因此设置 lo = mid + 1。当 lo 与 hi 相等时，这个值就是答案。
在第一个示例中，范围初始为 1 到 10。速度为 5 时符合要求，因此范围变为 1 到 5；速度为 3 时需要 10 小时，因此范围变为 4 到 5；速度为 4 时需要 7 小时，因此范围变为 5 到 5。
算法
- 将
lo = 1设为 1，并将hi设为最大的一堆。 - 当
lo < hi时，取mid = lo + (hi - lo) / 2。 - 计算速度为
mid时所需的小时数：对每一堆，将(pile + mid-1) / mid加到 64 位总数中。 - 如果总数至多为
h，就将hi = mid；否则将lo = mid + 1。 - 返回
lo。
def minEatingSpeed(piles, h):
lo, hi = 1, max(piles) # the largest pile always works: one hour per pile
while lo < hi:
mid = lo + (hi - lo) // 2
hours = 0
for pile in piles:
hours += (pile + mid - 1) // mid
if hours <= h:
hi = mid # mid works, so the answer is mid or slower
else:
lo = mid + 1 # mid is too slow, so the answer is faster
return lo
易错点和边界情况
- 小时数溢出。速度为 1 时，5000 堆
10^9根香蕉需要5 × 10^12小时，超过 32 位整数的上限，溢出后的总小时数可能会让较慢的速度通过检查。使用 64 位整数计数，或者在总小时数超过h后停止计数。 - 向下取整。
10 / 4得到 2，但吃完那堆香蕉需要 3 小时。 - 从 0 开始搜索范围。这样
mid可能为 0，导致计数时除以 0。 - 当
mid符合条件时，设置hi = mid - 1。这样可能会排除答案。 - 将
hi设得低于最大的一堆香蕉数量。当h等于堆数时，所有更低的速度都不符合条件，搜索结果就会落在其中一个速度上。
常见问题3
吃香蕉的 Koko 算法的时间复杂度是多少？
二分查找的时间复杂度为 O(n log m)，其中 n 是堆的数量，m 是最大堆的大小：大约需要检查 log2(m) 次，当 m = 10^9 时为 30 次，每次都会读取所有堆各一次。额外空间复杂度为 O(1)。
速度的下限和上限分别是多少？
上界是最大的那堆香蕉：当速度达到这个值时，每堆香蕉都只需要 1 小时，肯定来得及。下界是 1。你可以把下界提高到香蕉总数除以 h 后向上取整的结果，因为 Koko 每小时最多吃 k 根香蕉。
如何用整数进行除法并向上取整？
使用 (p + k-1) / k 并进行整数除法。加上 k-1 会将任何余数推到下一个 k 的倍数之后，而整除时结果保持不变：速度为 4 时，10 得到 13 / 4 = 3；8 得到 11 / 4 = 2。不需要浮点数。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def minEatingSpeed(piles, h):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
piles = [4, 10, 7, 3] h = 6
预期输出
5