題目描述:珂珂喜歡吃香蕉,有 n 堆香蕉,第 i 堆有 piles[i] 根。守衛將在 h 小時後回來。珂珂每小時可以選擇一堆香蕉,以速度 k 根/小時吃,若該堆少於 k 根則全部吃完(不會換下一堆)。請找出讓珂珂在 h 小時內吃完所有香蕉的最小速度 k。
解題思路:這道題的核心是「二分搜尋答案」。速度 k 的範圍是 [1, max(piles)]:最慢每小時吃 1 根,最快每小時吃最大堆的數量(一小時吃完最大堆)。
觀察到一個單調性:若速度 k 可以在 h 小時內吃完,那速度 k+1 也一定可以。因此可以對速度進行二分搜尋。
驗證函數:給定速度 k,計算吃完所有香蕉需要的總時間 = Σ ⌈piles[i] / k⌉(向上取整)。若總時間 ≤ h,則速度 k 可行。
二分搜尋:在 [1, max(piles)] 範圍內搜尋最小的可行速度。每次取中間值 mid,若可行則嘗試更小(hi = mid),否則增加速度(lo = mid + 1)。
時間複雜度:O(n log M) — 其中 n 是香蕉堆數,M 是最大堆的數量(即速度的搜尋上界)。二分搜尋需要 O(log M) 次迭代,每次驗證需 O(n) 時間。
空間複雜度:O(1) — 除輸入陣列外,僅使用常數個額外變數。
1. Set lo = 1, hi = max(piles) 2. While lo < hi: a. Compute mid = lo + (hi - lo) / 2 b. Compute total_hours = sum of ceil(pile / mid) for each pile c. If total_hours <= h: hi = mid // mid is feasible, try smaller d. Else: lo = mid + 1 // mid too slow, need faster 3. Return lo
線性掃描 O(M×n):從速度 1 開始逐一測試每個速度,找到第一個可行的速度即為答案。正確但效率極差,當 M 很大時無法通過時間限制。
利用數學上界收緊搜尋範圍:由於 h ≥ n(至少每堆要吃一小時),可以將上界從 max(piles) 進一步縮小。但最壞情況下上界仍是 max(piles),漸進複雜度不變,只是常數較小。
piles 陣列已排序,是否能進一步優化驗證函數的效率?