# 【Day 26】爱吃香蕉的珂珂
# 题目描述
珂珂喜欢吃香蕉。这里有 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/koko-eating-bananas
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
# 解法一
# 时间复杂度 O(m*n) 两个循环 n 为数组长度，m 为 k--次数
# 空间复杂度 O(1) 创建了 2 个新的空间
暴力法超时了
var minEatingSpeed = function(piles, H) {
let k = Math.max(...piles);
while (true) {
let count = 0;
for (let i = 0; i < piles.length; i++) {
count += Math.ceil(piles[i] / k);
}
if (count > H) return k + 1;
k--;
}
};
# 解法二
# 时间复杂度 O(m*logn) m 为数组长度，logn 是二分次数
# 空间复杂度 O(1) 创建了 2 个新的空间
第一次超时了，然后实际上 k 是一个 0-max（...piles)的有序数组，查找其中合适的一个值，那么就可以使用二分法
function isEatAll(piles, H, k) {
let count = 0;
for (let i = 0; i < piles.length; i++) {
count += Math.ceil(piles[i] / k);
}
return count > H;
}
var minEatingSpeed = function(piles, H) {
let right = Math.max(...piles);
let left = 0;
while (left <= right) {
let mid = ~~((left + right) / 2);
if (isEatAll(piles, H, mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
};
# 参考回答
# 题目地址（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^4 piles.length <= H <= 10^9 1 <= piles[i] <= 10^9# 前置知识
- 二分查找
# 思路
符合直觉的做法是，选择最大的堆的香蕉数，然后试一下能不能行，如果不行则直接返回上次计算的结果，如果行，我们减少 1 个香蕉，试试行不行，依次类推。计算出刚好不行的即可。这种解法的时间复杂度比较高，为 $O(N * M)$，其中 N 为 piles 长度， M 为 Piles 中最大的数。。
这道题如果能看出来是二分法解决，那么其实很简单。为什么它是二分问题呢？我这里画了个图，我相信你看了就明白了。
香蕉堆的香蕉个数上限是 10^9， 珂珂这也太能吃了吧？
# 关键点解析
- 二分查找
# 代码
代码支持：Python，JavaScript
Python Code:
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 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 模块。
