难度：★★★☆☆
类型：数组
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

珂珂喜欢吃香蕉。这里有 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

解答

审题发现，速度是一个整数（有限搜索空间），并且有最大和最小范围，需要我们寻找到一个临界点，很显然这类问题是要用二分法解决的。

【初始情况】
女孩吃香蕉的最小速度为1，最大速度为数组中的最大值。

【边界条件】
女孩速度较大时，一定可以快速吃完，而不被抓住，如果速度慢到一定程度，吃不完，会被抓，抓与被抓的临界点在于，速度可以刚好满足在指定时间内吃完。

因此我们可构造一个函数，函数的输入是吃香蕉的速度speed，函数返回值是以该速度吃香蕉会不会被抓住，会被抓住返回False。

然后就是二分法的模板：

    while 下限< 上限:
        中点 = (下限+上限) // 2
        if 成功吃完所有香蕉以(中点)速度:
            上限 = 中点
        else:
            下限 = 中点 + 1

from typing import List
import math


class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        slow, fast = 1, max(piles)

        def possible(speed):
            return sum([math.ceil(pile / speed) for pile in piles]) <= H

        while slow < fast:
            mid = (slow + fast) // 2
            if possible(mid):
                fast = mid
            else:
                slow = mid + 1

        return slow

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析