问题
https://leetcode-cn.com/problems/koko-eating-bananas
珂珂喜欢吃香蕉。这里有 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
解法
如果是暴力来查找最慢的速度的话，那么需要遍历所有可能的速度，在每个速度的情况下，检查是否可以吃完。
最小速度为1。
最大速度为吃最多的那一堆，即 max(piles)。
上面的思路，其实是个空间线性搜素的问题，可以使用二分查找来优化时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import math
def get_min_eat_speed(piles: list, hours: int):
min_speed = 1 # 最少吃1个
max_speed = max(piles) + 1 # 最多吃最大的一堆，+1 用于扩充查找的边界
while min_speed < max_speed:
mid_speed = (min_speed + max_speed) // 2
if can_eat_complete(piles, mid_speed, hours):
# 能吃完，再尝试放慢速度看能否吃完，往小缩小范围
max_speed = mid_speed
else:
# 不能吃完，因为吃的太慢了，再吃快些，往大缩小范围
min_speed = mid_speed + 1
return min_speed
def can_eat_complete(piles: list, speed: int, hours: int) -> bool:
"""
检查能否吃完
:param piles:香蕉
:param speed: 吃香蕉速度
:param hours:限制的小时
:return:能否吃完
"""
t = 0
for p in piles:
# 每堆需要吃至少一个小时，因为 “如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。”
t += math.ceil(p / speed)
return t <= hours
if __name__ == '__main__':
# piles = [30, 11, 23, 4, 20]
# hours = 5
banana_piles = [3, 6, 7, 11]
leave_hours = 8
print(get_min_eat_speed(banana_piles, leave_hours)) # 4
时间复杂度：\(O(nlogn)\)