[python 刷题] 875 Koko Eating Bananas

[python 刷题] 875 Koko Eating Bananas

题目：

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.

这道题主要有几个限制：

1. koko 想要吃完 n piles 个香蕉
2. koko 吃香蕉的速度是匀速的
3. 不管 koko 吃得多快，她吃完 1 pile 就不会继续吃了
4. koko 希望吃得越慢越好
5. koko 需要在 h 小时内吃完
6. piles.length <= h，也就是说 koko 一定能吃完所有 pile 的香蕉

换言之，koko 每小时需要尽可能少吃香蕉，并且保证在 h 小时内吃完所有香蕉，这道题的暴力解为：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        speed = 1

        def hour_needed_to_eat():
            total_hour_needed = 0
            for pile in piles:
                total_hour_needed += math.ceil(pile / speed)
                if total_hour_needed > h:
                    return False

            return total_hour_needed <= h

        while True:
            if hour_needed_to_eat():
                return speed
            speed += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

也就是让 koko 从每小时 1 根香蕉开始吃起，一直吃到正好在 h 小时内可以吃完香蕉的速度就返回

尽管循环的条件是 while True，不过已经得知 piles.length <= h，所以香蕉的吃速上限为 max(piles)，换言之，这道题可以理解成，在 $[1,2,3,...,max(piles)]$ 这样一个有序数组内，找到一个特定的解，所以暴力解的空间复杂度为 $O(1)$，时间复杂度为 $O(max(piles)\times n)$，其中 $n$ 为数组的长度。

另外，看到 在一个有序数组中找到一个特定的解 这样的 pattern，大概是能够比较模糊的猜测出，这道题是一道 binary search，这道题的要求就是在 $[1,2,3,...,max(piles)]$ 中找到一个最小的数字，使得 ${\sum }_{i=1}^{max(piles)}math.ceil(\frac{pile}{i})$ 趋近于给定的 $h$

将暴力解的写法稍微改动一下，变成 binary search：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r

        def hour_needed_to_eat(k):
            total_hour_needed = 0
            for pile in piles:
                total_hour_needed += math.ceil(pile / k)

            return total_hour_needed

        while l <= r:
            m = (l + r) // 2
            hours_needed = hour_needed_to_eat(m)

            if hours_needed <= h:
                r = m - 1
                res = m
            else:
                l = m + 1

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

因为使用了二分算法，这道题的时间复杂度为 $O(n\times log(max(piles)))$