<div>
Koko loves to eat bananas. There are n piles of bananas, the i<sup>th</sup> pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
<pre>Input: piles = [3,6,7,11], h = 8 Output: 4 </pre>
Example 2:
<pre>Input: piles = [30,11,23,4,20], h = 5 Output: 30 </pre>
Example 3:
<pre>Input: piles = [30,11,23,4,20], h = 6 Output: 23 </pre>
Constraints:
1 <= piles.length <= 10<sup>4</sup>piles.length <= h <= 10<sup>9</sup>1 <= piles[i] <= 10<sup>9</sup>
</div>
题目大意：
猴子吃n堆香蕉，要在h小时内吃完，求每小时吃的最少k根才能在限定时间内全部吃完。
解题思路：
枚举法，如果对于[3,6,7,11], k=3, 怎么算出多少小时呢? 数组每个数除以k向上取整求和即可，O(n)完成。怎么可以更快找到答案呢，很明显是二分法logn找答案，每次用O(n)算实际吃了多少小时。总的复杂度是O(nlogn).
所以此题是数值二分法，我也曾想过排序，但排序只能影响计算小于k值的小时数，不能优化后半段的，所以不用排序，而且数值二分法也不要求排序。
解题步骤：
数值二分法模板
注意事项：
- start是从1开始，不是min(piles)。最大值取max(piles)因为跟取整型最大值是一样的。这样也可以避免单独处理单元素数组。
- epsilon取0.5. 一般整数题都取0.5
- mid是除2获得不是//2
- mid作为参数输入到get_hours()要去int(mid)与题目一致，因为题目的k是整数
- 模板中h==hours时，不能return，要继续在左半区找，因为要达到误差epsilon内才会停止。类似于first_position
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def minEatingSpeed(self, piles: List[int], h: int) -> int:
#if len(piles) == 1: # attn
# return math.ceil(piles[0] / h)
# piles.sort()
def get_hours(piles, k):
return sum([math.ceil(n / k) for n in piles])
# start, end = piles[0], piles[-1] # 3, 4
start, end = 1, max(piles) # attn: 1 rather than min(piles)
while start + 0.5 < end: # attn: use 0.5
mid = start + (end - start) / 2 # attn /2 not // 2 | 7, 5, 4
hours = get_hours(piles, int(mid)) # attn: int(mid) | 5, 8, 8
if h >= hours: # eat slower, attn 8 > 5
end = mid # end=7, 5, 4
else:
start = mid
算法分析：
next时间复杂度为O(nlogn)，空间复杂度O(n)
