LC875- 爱吃香蕉的珂珂

「link」

img

---

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

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

因为每堆香蕉的耗时就为$ \(，因此总耗时也可以求得为\)ans = _{i=1}^n{ }$。

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

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

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

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

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)\)。