0875. 愛吃香蕉的珂珂 · ttttt

# 0875. 愛吃香蕉的珂珂 ## 題目地址（875. 愛吃香蕉的珂珂） <https://leetcode-cn.com/problems/koko-eating-bananas/description/> ## 題目描述 ``` <pre class="calibre18">``` 珂珂喜歡吃香蕉。這里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警衛已經離開了，將在 H 小時后回來。珂珂可以決定她吃香蕉的速度 K （單位：根/小時）。每個小時，她將會選擇一堆香蕉，從中吃掉 K 根。如果這堆香蕉少于 K 根，她將吃掉這堆的所有香蕉，然后這一小時內不會再吃更多的香蕉。珂珂喜歡慢慢吃，但仍然想在警衛回來前吃掉所有的香蕉。返回她可以在 H 小時內吃掉所有香蕉的最小速度 K（K 為整數）。示例 1：輸入: piles = [3,6,7,11], H = 8 輸出: 4 示例 2：輸入: piles = [30,11,23,4,20], H = 5 輸出: 30 示例 3：輸入: piles = [30,11,23,4,20], H = 6 輸出: 23 提示： 1 <= piles.length <= 10^4 piles.length <= H <= 10^9 1 <= piles[i] <= 10^9 ``` ``` ## 前置知識 - 二分查找 ## 公司 - 字節 ## 思路符合直覺的做法是，選擇最大的堆的香蕉數，然后試一下能不能行，如果不行則直接返回上次計算的結果，如果行，我們減少 1 個香蕉，試試行不行，依次類推。計算出剛好不行的即可。這種解法的時間復雜度比較高，為 O(N?M)O(N \* M)O(N?M)，其中 N 為 piles 長度， M 為 Piles 中最大的數。。這道題如果能看出來是二分法解決，那么其實很簡單。為什么它是二分問題呢？我這里畫了個圖，我相信你看了就明白了。 ![](https://img.kancloud.cn/4b/04/4b045d9a3ad9eba0ca9ac4c3d7301b3d_936x787.jpg) > 香蕉堆的香蕉個數上限是 10^9，珂珂這也太能吃了吧？ ## 關鍵點解析 - 二分查找 ## 代碼代碼支持：Python，JavaScript Python Code: ``` <pre class="calibre18">``` class Solution: def canEatAllBananas(self, piles, H, K): t = 0 for pile in piles: t += math.ceil(pile / K) return t <= H def minEatingSpeed(self, piles: List[int], H: int) -> int: l, r = 1, max(piles) # [l, r) ，左閉右開的好處是如果能找到，那么返回 l 和 r 都是一樣的，因為最終 l 等于 r。 while l < r: mid = (l + r) >> 1 if self.canEatAllBananas(piles, H, mid): r = mid else: l = mid + 1 return l ``` ``` JavaScript Code: ``` <pre class="calibre18">``` function canEatAllBananas(piles, H, mid) { let h = 0; for (let pile of piles) { h += Math.ceil(pile / mid); } return h <= H; } /** * @param {number[]} piles * @param {number} H * @return {number} */ var minEatingSpeed = function (piles, H) { let lo = 1, hi = Math.max(...piles); // [l, r) ，左閉右開的好處是如果能找到，那么返回 l 和 r 都是一樣的，因為最終 l 等于 r。 while (lo <= hi) { let mid = lo + ((hi - lo) >> 1); if (canEatAllBananas(piles, H, mid)) { hi = mid - 1; } else { lo = mid + 1; } } return lo; // 不能選擇hi }; ``` ``` **復雜度分析** - 時間復雜度：O(max(N,N?logM))O(max(N, N \* logM))O(max(N,N?logM))，其中 N 為 piles 長度， M 為 Piles 中最大的數。 - 空間復雜度：O(1)O(1)O(1) ## 模板分享幾個常用的的二分法模板。 ### 查找一個數 ``` <pre class="calibre18">``` public int binarySearch(int[] nums, int target) { // 左右都閉合的區間 [l, r] int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if (nums[mid] < target) // 搜索區間變為 [mid+1, right] left = mid + 1; else if (nums[mid] > target) // 搜索區間變為 [left, mid - 1] right = mid - 1; } return -1; } ``` ``` ### 尋找最左邊的滿足條件的值 ``` <pre class="calibre18">``` public int binarySearchLeft(int[] nums, int target) { // 搜索區間為 [left, right] int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索區間變為 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索區間變為 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收縮右邊界 right = mid - 1; } } // 檢查是否越界 if (left >= nums.length || nums[left] != target) return -1; return left; } ``` ``` ### 尋找最右邊的滿足條件的值 ``` <pre class="calibre18">``` public int binarySearchRight(int[] nums, int target) { // 搜索區間為 [left, right] int left = 0 int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索區間變為 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索區間變為 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收縮左邊界 left = mid + 1; } } // 檢查是否越界 if (right < 0 || nums[right] != target) return -1; return right; } ``` ``` > 如果題目重點不是二分，也就是說二分只是眾多步驟中的一步，大家也可以直接調用語言的 API，比如 Python 的 bisect 模塊。更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)