# 0875. 爱吃香蕉的珂珂
### 题目地址（875. 爱吃香蕉的珂珂）
### 题目描述
```
珂珂喜欢吃香蕉。这里有 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-solution/91/binary-search.md)
### 公司
* 字节
### 思路
符合直觉的做法是，选择最大的堆的香蕉数，然后试一下能不能行，如果不行则直接返回上次计算的结果，如果行，我们减少 1 个香蕉，试试行不行，依次类推。计算出刚好不行的即可。这种解法的时间复杂度比较高，为 $O(N \* M)$，其中 N 为 piles 长度， M 为 Piles 中最大的数。。
这道题如果能看出来是二分法解决，那么其实很简单。为什么它是二分问题呢？我这里画了个图，我相信你看了就明白了。
> 香蕉堆的香蕉个数上限是 10^9， 珂珂这也太能吃了吧？
### 关键点解析
* 二分查找模板
### 代码
代码支持：Python，JavaScript
Python Code:
```py
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 l
```
JavaScript Code:
```js
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)$
### 模板
分享几个常用的的二分法模板。
#### 查找一个数
```java
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;
}
```
#### 寻找最左边的满足条件的值
```java
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;
}
```
#### 寻找最右边的满足条件的值
```java
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 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/875.koko-eating-bananas.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.