LeetCode

Appearance

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.

 

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

 

Constraints:

  • 1 <= piles.length <= 104
  • piles.length <= h <= 109
  • 1 <= piles[i] <= 109
Related Topics
  • 数组
  • 二分查找

  • 👍 691
  • 👎 0

    • 解法 ​

    二分查找法

    • 有序才能使用二分查找
    • 确定二分的边界在哪里

    本题中二分的边界在最小吃的香蕉数是1， 最大是整个数组的最大值

    py
    # leetcode submit region begin(Prohibit modification and deletion)
import math
from math import ceil
from typing import List

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

        min_k = 1
        max_k = max(piles)


        while min_k < max_k:
            mid_k = (min_k + max_k) // 2

            last_h = sum(ceil(p / mid_k) for p in piles)

            if last_h > h:
                min_k = mid_k + 1
            else:
                max_k = mid_k

        return min_k

        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度O(N)
      • N = plies.length + log(max(plies))
    • 空间复杂度O(1)