LeetCode 875. [Python] Koko Eating Bananas [Facebook]
原题链接
中等
作者:
徐辰潇
,
2021-02-07 10:13:56
,
所有人可见
,
阅读 266
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
#Binary search
#the lower bound for K is 1, i.e. koko eats 1 banana every hour
#the lower bound for K is max(piles)
#usning binary search, found a position K
#TC: O(log(max(piles))*len(piles))
#SC: O(1)
n = len(piles)
left = 1
right = max(piles)
def help(k):
count = 0
for banana in piles:
count += math.ceil(banana/k)
if count > H:
return False
return count <= H
while(left + 1 < right):
middle = left + (right - left) // 2
Bool = help(middle)
if Bool:
right = middle
else:
left = middle
if help(left):
return left
else:
return right