大厂算法面试题《爱吃香蕉的猩猩》：既想舒舒服服的吃香蕉，又想在规定时间内吃完香蕉，猩猩该如何通过它的聪明才智做到呢？快来一起学习吧！

一、题目

珂珂喜欢吃香蕉。这里有 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

leetcode

二、分析

题目求的是最小速度吃香蕉，猩猩能懒则懒，只要保证在警卫回来前吃完就行

贪图的不是吃的有多快，贪图的是在规定时间内以最小速度吃完即可

最小速度怎么求？先搞定速度怎么求？

先找出每堆香蕉中的最多的香蕉数（R）是多少？然后从1~R香蕉数范围内二分，求出中间位置的香蕉数，就是每小时吃的香蕉数，也就是吃的速度（每小时吃这么多根香蕉），以这个速度吃完所有香蕉需要的时间是多少？

怎么算每堆吃完的时间？每一堆香蕉吃完的时间为每一堆的香蕉数除以吃的速度，向上取整

如果吃完的时间大于警卫回来的时间，则吃的速度太慢，需要加大吃香蕉的速度，即需要吃更多的香蕉数（L = M + 1），如果吃完时间小于等于警卫回来的时间，则当前吃的速度还可以，但是猩猩又太懒，不想吃那么快，则减少吃的香蕉（R = M - 1），看能不能还满足时间要求，这不就是二分么！！！

猩猩吃完一堆的香蕉所需要的时间是多少？利用公式计算或者工具类，比如想达到 7/2 等于 4的效果，怎么弄？result = (7+2-1) / 2 = 4，比如 8/2 = (8+2-1) / 2 = 4

这猩猩太聪明了，既能慢慢悠悠的吃，又能吃完所有香蕉，真是聪明绝顶！

三、实现

public static int minEatingSpeed(int[] piles, int h) {
    int L = 1;
    int R = 0;
    // 找出每堆中的最大香蕉数
    for (int pile : piles) {
        R = Math.max(R, pile);
    }
    int ans = 0;
    int M = 0;
    while (L <= R) {
        M = L + ((R - L) >> 1);
        if (hours(piles, M) <= h) {
            ans = M;
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    return ans;
}

// 以speed的速度吃完所有香蕉，需要几个小时
// 时间向上取整
public static int hours(int[] piles, int speed) {
    int ans = 0;
    int offset = speed - 1;
    for (int pile : piles) {
        ans += (pile + offset) / speed;
    }
    return ans;
}