[数据结构与算法]LeetCode 875. Koko Eating Bananas - 二分查找（Binary Search）系列题20

Koko loves to eat bananas. There are?n?piles of bananas, the?ith?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:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

这题跟LeetCode 1760. Minimum Limit of Balls in a Bag?是一样的题型，只是变成了猴子吃香蕉。熟练掌握二分查找法就可以搞定Leetcode上所有这一类型的题。

题目大意：给定一个数组piles, 数组的长度n表示有n堆香蕉，第i个元素表示第i堆里有piles[i]根香蕉。现在猴子Koko想趁管理员离开时偷吃香蕉，管理将离开h小时。猴子Koko很聪明可以自己决定吃香蕉的速度k根每小时，即每个小时它可以选一堆香蕉来并吃掉k根，如果这堆香蕉根数多于k根它最多只能吃掉k根，剩下的只能在下次选到时再吃，如果这堆香蕉根数少于k根那没办法它也只能把这堆香蕉全吃掉然后停下而不能再吃其它堆里的香蕉，只能等到下个小时再选一堆来吃。现在猴子想在每个小时里尽可能慢点吃不至于撑到（k尽可能小）但又想在h小时内把所有香蕉吃完。求最慢的吃香蕉速度也就是最小的k。

搞懂题目就会发现其实这题跟LeetCode 1760. Minimum Limit of Balls in a Bag?一模一样。最理想的状态就是每个小时只吃一根慢慢吃；最不理想的状态香蕉可能很多，为了不至于来不及需要每个小时把整堆香蕉全吃光，那么速度k就是最大堆的香蕉根数。因此我们要做的就是从1到piles里的最大值maxNum的区间范围内找到一个最小的且满足条件的值，这很自然地想到了二分查找法。

取[1, maxNum]的中间值mid=(1 + maxNum) // 2，计算当速度为mid根每小时要吃几个小时才能把所有香蕉吃完，要是总时间小于等于h小时，说明还有可能吃更慢点，则继续在左半区间查找可能的更慢的速度；要是总时间大于h小时说明无法吃完所有香蕉，则继续在右半区间查找更快的速度。

如何判断速度为mid 时需要几个小时才能吃完所有香蕉？遍历整个数组piles，如果香蕉根数num小于等于mid则只需要1个小时，如果香蕉根数num大于mid，则需要小时数为(num - 1) // mid + 1。

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        
        while l <= r:
            mid = (l + r) // 2
            hours = 0
            for b in piles:
                hours += (b - 1) // mid + 1
            if hours <= h:
                r = mid - 1
            else:
                l = mid + 1
        
        return l

?

?