Last Updated on 2022-01-20 by Clay
題目
Koko loves to eat bananas. There aren
piles of bananas, theith
pile haspiles[i]
bananas. The guards have gone and will come back inh
hours. Koko can decide her bananas-per-hour eating speed ofk
. Each hour, she chooses some pile of bananas and eatsk
bananas from that pile. If the pile has less thank
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 integerk
such that she can eat all the bananas withinh
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