875. 爱吃香蕉的珂珂(Medium)

题目描述

总共有 $N$ 堆香蕉，每次珂珂只能吃一堆，找到珂珂在 $H$ 小时内吃掉香蕉的最小速度。

注：如果这堆香蕉少于 $K$ 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

样例

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

题解

二分查找：明确一点，本题寻找的是靠右的值

Python示例

# 模板1
import math
class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        def get_hours(k):
            hours = 0 
            for pile in piles:
                hours += math.ceil(pile / k)
            return hours
        
        # 更简洁的写法
        # def get_hours(k):
        #    return sum(( p - 1) // k + 1 for p in piles) 

        left, right = 1, max(piles)
        ans = 0
        while left <= right:
             mid = math.ceil((left + right) / 2) # 向右取整
             if get_hours(mid) <= H: # 吃的快，慢一点找到最小的速度
                 ans = mid 
                 right = mid - 1
             else:
                 left = mid + 1
        return ans 

# 模板2 左闭右开，找到的值是靠右的
import math
class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        def get_hours(k):
            hours = 0 
            for pile in piles:
                hours += math.ceil(pile / k)
            return hours

        left, right = 1, max(piles) + 1
        ans = 0
        while left < right:
             mid = (left + right) >> 1
             if get_hours(mid) <= H: # 吃的快，慢一点找到最小的速度
                 right = mid
             else:
                 left = mid + 1
        return left