875. Koko Eating Bananas

source: https://leetcode.com/problems/koko-eating-bananas/

Question

Koko loves to eat bananas. There are n piles of bananas, the ith 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 will not eat any more bananas during this hour.

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

Return the minimum integer k such that she can eat all the bananas within h hours.

暴力法

根据题意，可以比较简单的写出暴力法，从K为最小值开始，一个个的去算时间，当找到第一个符合要求的K时返回。

/**
 * 暴力法
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
    let K = 1;
    while (true) {
        const total = piles.reduce((acc, crr) => Math.ceil(crr / K) + acc, 0);
        if (total <= h) return K;
        K += 1;
    }
};

二分查找

暴力法会耗时的主要原因是每次都是+1，一个个的去算结果。既然知道左右极值，就可以用左边界二分查找法去优化。

当total > h时，说明K的值还太小，缩小左边界。

/**
 * 二分查找
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
    let left = 1;
    let right = 10 ** 9;
    while (left <= right) {
        const mid = ~~((left + right) / 2);
        const total = piles.reduce((acc, crr) => Math.ceil(crr / mid) + acc, 0);
        if (total === h) right = mid - 1;
        else if (total > h) left = mid + 1;
        else right = mid - 1;
    }
    return left;
};

End

先写出暴力法，然后伺机优化，在探索阶段比较容易发现题目的思路。