LeetCode: 875-Koko Eating Bananas 解題紀錄

Last Updated on 2022-01-20 by Clay

題目

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

Koko 喜歡吃香蕉（Koko 是什麼東西啊......）而題目會告訴我們香蕉在第 i 串上有 piles[i] 條香蕉。假設守衛會在 h 小時後回來。假設 Koko 一小時間能吃 k 根香蕉，並在吃完一串後無法在同一小時內吃另外一串 —— Koko 最慢能以多慢的速度吃完所有香蕉呢？

我們要做的就是計算出這個 k 值並回傳。

---

解題思路

我一開始乾脆地嘗試了從 1 開始計算起並逐次往上加一來搜尋 k 值。但很顯然地馬上遇到了 TLE 的瓶頸。

這種時候，果然該用二元搜索（binary search）。先令最小值為 1、再令最大值為香蕉串中最大的值（畢竟如果最大值都無法在時限內吃完，那打從一開始就吃不完所有香蕉了）。接著從最大值與最小值之間的中間值開始計算起，如果可以順利吃完，則將最大值移動至『中間值-1』，反之則將最小值移動至『中間值+1』...... 接著計算全新的中間值。

就是很經典的二元搜索法，因為一次可以淘汰掉一半的可能性，所以時間複雜度比較低。

複雜度

n 為香蕉串數（列表長度），m 為最大值（畢竟可視為是從 [1, m] 列表做二元搜索）

Time Complexity	O(nlog(m))
Space Complexity	O(1)

C++ 範例程式碼

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        // Init
        int l = 1;
        int r = *max_element(piles.begin(), piles.end());
        
        // Binary search
        while (l <= r) {
            // Settings
            int mid = l + ((r - l) / 2);
            int _h = 0;
            bool tooMuchTime = false;
            
            // Check the cost time
            for (int pile: piles) {
                _h += pile / mid;
                if (pile % mid != 0) ++_h;
                if (_h > h) {
                    tooMuchTime = true;
                    break;
                }
            }
            
            // If use too much time, left move to middle + 1; else, right move to middle -1 ;
            if (tooMuchTime) l = mid + 1;
            else r = mid - 1;
        }
        
        return l;
    }
};

Python 範例程式碼

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Init
        l = 1
        r = max(piles)
        
        # Binary search
        while l <= r:
            # Settings
            mid = l + ((r - l) / 2)
            _h = 0
            tooMuchTime = False
            
            # Check the cost time
            for pile in piles:
                _h += pile // mid
                if pile % mid != 0: 
                    _h += 1
                if _h > h:
                    tooMuchTime = True
                    break
            
            # If use too much time, left move to middle + 1; else, right move to middle -1 ;
            if tooMuchTime: l = mid + 1
            else: r = mid - 1
        
        return l

---

References

• https://leetcode.com/problems/koko-eating-bananas/

---

Read More

• LeetCode 解題紀錄目錄