875. 爱吃香蕉的珂珂

Difficulty
Medium
Tags
二分查找
URL
https://leetcode-cn.com/problems/koko-eating-bananas/
Star
珂珂喜欢吃香蕉。这里有 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
通过次数48,330提交次数100,464

二分法

思路
虽然还不知道狒狒1小时至少要吃几根香蕉才能在门卫回来之前吃完所有的香蕉，但知道它吃香蕉的速度的范围。显然，它每小时至少要吃1根香蕉。由于它1小时内只吃一堆香蕉，因此它每小时吃香蕉数目的上限是最大一堆香蕉的数目，记为max根。
然后用二分法具体求解最慢的速度
题解
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)

        while left <= right:
            # 以mid 速度吃需要时间 time
            mid = left + (right - left)//2
            time = self.needTime(piles, mid)
            # 用的时间太长了 ，需要加快速度
            if time > h:
                left = mid + 1
            # 吃太快了，减慢速度
            elif time < h:
                right = mid - 1
            # 时间刚刚好，那就看看还能不能再降低速度
            elif time == h:
                right = mid - 1
        return left

    def needTime(self, piles, speed):
        time = 0
        for pile in piles:
            if pile % speed == 0:
                time += pile // speed
            else:
                time += (pile // speed) + 1

        return time



# ---------- 优化------------
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)

        while left <= right:
            # 以mid 速度吃需要时间 time
            mid = left + (right - left)//2
            time = self.needTime(piles, mid)
            # 用的时间太长了 ，需要加快速度
            if time > h:
                left = mid + 1
            # 吃太快了，减慢速度
            elif time <= h:
                right = mid - 1
        return left

    def needTime(self, piles, speed):
        time = 0
        for pile in piles:
            time += (pile + speed - 1) // speed
        return time