Leetcode 875 Koko Eating Bananas

发表于 |

Koko loves to eat bananas. There are N piles of bananas, the i-th 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 won’t eat any more bananas during this hour.
Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer K such that she can eat all the bananas within H hours.

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

Example 2:
Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:
Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

  1. 1 <= piles.length <= 10^4
  2. piles.length <= H <= 10^9
  3. 1 <= piles[i] <= 10^9

分析：

  1. 去找一个值满足某种条件，这种题见得太多了，显然是二分法，之后我整理一下所有的这种题目做一个合辑。
  2. 那么这里怎么选定初始的lo和hi呢？我们要明确我们找的是吃的速度，那么最低，起码得在吃吧，所以起码lo = 1，那hi呢？我们注意到note中第二点pile.length <= H，因为我们吃的速度就算再快，一次也只能吃一盘而已，所以无论怎样最少都得pile.length个小时才能吃完，所以hi = max(piles)

思路：

  1. 对于某个确定的k值，我们如何计算吃完所有pile需要的时间呢，对于一盘，时间应该是piles[i]/k 向上取整，然后求和判断是否大于H
  2. 若小于，则说明吃完还绰绰有余，还可以吃慢一点，从lo,mid中继续找
  3. 若大于，则说明吃得太慢了，则应该从mid,hi中继续找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# O(NlogM) time，N = len(piles), M = max(piles)
class Solution(object):
    def minEatingSpeed(self, piles, H):
        """
        :type piles: List[int]
        :type H: int
        :rtype: int
        """
        lo,hi = 1,max(piles)
        def canEat(k):
            time = 0
            for i in range(len(piles)):
                time += int(math.ceil(piles[i]/float(k)))
                if time > H: return False
            return True
        while lo < hi:
            mid = (lo + hi) // 2
            if canEat(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

113 / 113 test cases passed.
diffculty: medium
Runtime: 824 ms