爱吃香蕉的珂珂

题目链接

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例:

输入: piles = [3,6,7,11], H = 8
输出: 4

思路

解法一：

该题与1011. 在 D 天内送达包裹的能力 类似，一样的思路

  1. 找出速度的区间，最小值为1，因为piles.length <= H，所以速度最大值为数组的最大值；
  2. 使用二分法寻找速度的最佳取值
import math
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        while left < right:
            mid = left + (right - left) // 2
            if self.check(piles, mid, h): # 满足条件，向速度小的值靠拢
                right = mid
            else: # 不满足条件，向速度大的值靠拢
                left = mid + 1
        return right

    def check(self, piles, mid, h): # 检查速度为mid时，能否在h小时内吃完
        n = len(piles)
        i = 0
        total = 0
        while i < n:
            total += math.ceil(piles[i] / mid)
            i += 1
        return total <= h