LC875- 爱吃香蕉的珂珂

「link」

---

初看此题，还是没有什么思路，也是第一次见这种类型（二分答案）。

从正面考虑吃完所有香蕉的最小速度$k$并不好求，但若我们已知一个速度$k^{\prime }$，我们就可以知道能否在$h$小时内吃完这些香蕉。

因为每堆香蕉的耗时就为$\lceil \frac{pile}{k^{\prime }}\rceil$，因此总耗时也可以求得为$ans={\sum }_{i=1}^n\lceil \frac{pil{e}_i}{k^{\prime }}\rceil$。

因此我们就可以对$k$进行二分，在以$k$为分割点的数组上具有「二段性」。

小于$k$的值，总耗时$ans$必然不满足$ans\le h$；

大于等于$k$的值，总耗时必然满足$ans\le h$。

然后就是需要确定二分的范围，因为每堆香蕉最少需要耗费一个小时，因为二分的上边界即为最大香蕉数，接下来就是对速度$k$进行二分。

JAVA 复制

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int r = Integer.MIN_VALUE;
        for (int pile : piles) {
            r = Math.max(r, pile);
        }
        int l = 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid, piles, h)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }

    private boolean check(int mid, int[] piles, int h) {
        int tot = 0;
        for (int pile : piles) {
            tot += Math.ceil(pile * 1.0 / mid);
        }
        return tot <= h;
    }
}

时间复杂度$O(nlogn)$，空间复杂度$O(1)$。