875. Koko Eating Bananas

Leetcode link

题目简介

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */

题目给我们一个数字数组 piles 以及一个数字 h

piles 的每个元素代表有多少根香蕉，h 代表我们可以吃香蕉的总时间

我们可以自己选择每个小时要吃多少根香蕉，但是如果吃完了某一堆香蕉后，在当前的小时中就不允许吃别堆的香蕉了

最后需要我们返回我们最少每个小时吃多少根香蕉能在 h 小时内把所有香蕉吃完

解题思路

根据题意，我们至少需要 piles.length 个小时才能把所有香蕉吃完，并且每小时需要吃的香蕉数量为 Math.max(...piles)

题目要求我们让每个小时吃的香蕉数量最少，所以我们可以用二分搜索来一步步缩小每小时需要吃的香蕉数量的范围

具体的边界为：

• left = 1
• right = Math.max(...piles)

我们每次用二分搜索取得 mid 的值后，需要计算该 mid 下需要多少小时才能把全部香蕉吃完，假设是 time 小时

于是有两种情况：

• time <= h：此时我们记录当前的 mid，然后移动右边界
• time > h：此时我们移动左边界

这样一来，我们记录的符合条件的 mid 就会越来越小，直到无法满足题目要求的 h 小时

最后返回最后记录的 mid 即可

Javascript

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function(piles, h) {
    let left = 1
    let right = Math.max(...piles)
    let res = right

    while(left <= right) {
        const mid = Math.floor((left + right) / 2)
        const time = piles.reduce((acc, cur) => {
            return Math.ceil(cur/mid) + acc
        }, 0)

        if(time <= h) {
            res = mid
            right = mid-1
        } else {
            left = mid + 1
        }
    }
    return res
};

复杂度分析

n 代表 piles[i] 的最大值，m 代表 piles.length

时间

我们对 n 进行了二分搜索，所以是 O(logn)

每次二分搜索我们需要遍历一次 m，所以是 O(m)

合并后为 O(mlogn)

空间

O(1)