0875. 爱吃香蕉的珂珂
题目地址（875. 爱吃香蕉的珂珂）
https://leetcode-cn.com/problems/koko-eating-bananas/description/
题目描述
珂珂喜欢吃香蕉。这里有 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^4piles.length <= H <= 10^91 <= piles[i] <= 10^9前置知识
公司
字节
思路
符合直觉的做法是，选择最大的堆的香蕉数，然后试一下能不能行，如果不行则直接返回上次计算的结果，如果行，我们减少 1 个香蕉，试试行不行，依次类推。计算出刚好不行的即可。这种解法的时间复杂度比较高，为 $O(N * M)$，其中 N 为 piles 长度， M 为 Piles 中最大的数。。
这道题如果能看出来是二分法解决，那么其实很简单。为什么它是二分问题呢？我这里画了个图，我相信你看了就明白了。
香蕉堆的香蕉个数上限是 10^9， 珂珂这也太能吃了吧？
关键点解析
二分查找模板
代码
代码支持：Python，JavaScript
Python Code:
class Solution: def solve(self, piles, k): def possible(mid): t = 0 for pile in piles: t += (pile + mid - 1) // mid return t <= k l, r = 1, max(piles) while l <= r: mid = (l + r) // 2 if possible(mid): r = mid - 1 else: l = mid + 1 return lJavaScript Code:
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))$，其中 N 为 piles 长度， M 为 Piles 中最大的数。
空间复杂度：$O(1)$
模板
分享几个常用的的二分法模板。
查找一个数
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;}寻找最左边的满足条件的值
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;}寻找最右边的满足条件的值
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 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最后更新于
这有帮助吗？