> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/875-koko-eating-bananas.md).

# 875     Koko Eating Bananas

## 875. [Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/description/)

## 1. Question

Koko loves to eat bananas. There are`N` piles of bananas, the`i`-th pile has`piles[i]`bananas. The guards have gone and will come back in`H`hours.

Koko can decide her bananas-per-hour eating speed of`K`. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than`K`bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer`K`such that she can eat all the bananas within`H`hours.

**Example 1:**

```
Input: piles = [3,6,7,11], H = 8
Output: 4
```

**Example 2:**

```
Input: piles = [30,11,23,4,20], H = 5
Output: 30
```

**Example 3:**

```
Input: piles = [30,11,23,4,20], H = 6
Output: 23
```

**Note:**

* `1 <= piles.length <= 10^4`
* `piles.length <= H <= 10^9`
* `1 <= piles[i] <= 10^9`

## 2. Implementation

**(1) Binary Search**

* 这是最高级的二分查找题目，通过一个函数判断我们是否应该在左区间还是右区间查找。
* 首先题目要求我们找到一个最小的速度，使得能在H个小时内吃完所有piles里的香蕉。我们可以发现最小的速度是1，最大的速度则是piles里最大的pile，确定好范围后我们就可以进行二分查找
* 在二分过程中，我们通过getHours()得知以当前的rate吃完所有pile的香蕉需要多少时间，如果所需时间小于等于 H, 我们可以进一步降低rate, 将maxRate更新为targetRate, 否则所需时间超过H, 我们要提高rate, 将minRate更新为target + 1

```java
class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int minRate = 1, maxRate = Integer.MIN_VALUE;

        for (int pile : piles) {
            maxRate = Math.max(maxRate, pile);
        }

        while (minRate + 1 < maxRate) {
            int targetRate = minRate + (maxRate - minRate) / 2;

            int hours = getHours(piles, targetRate);

            if (hours > H) {
                minRate = targetRate + 1;
            }
            else {
                maxRate = targetRate;
            }
        }

        if (getHours(piles, minRate) <= H) {
            return minRate;
        }
        else {
            return maxRate;
        }
    }

    public int getHours(int[] piles, int rate) {
        int hours = 0;

        for (int pile : piles) {
            if (pile <= rate) {
                ++hours;
            }
            else if (pile % rate == 0) {
                hours += pile / rate;
            }
            else {
                hours += pile / rate + 1;
            }
        }
        return hours;
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(nlog(maxRate - 1)), 我们在\[1, maxRate]范围内进行二分查找，每找打一个targetRate,都会扫一遍piles数组确认所需要多少时间吃完所有pile的香蕉。 空间复杂度O(1)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/875-koko-eating-bananas.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.