中等

问题描述

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

提示：

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

二分查找

根据提示信息可以知道，警卫离开的时间是大于香蕉堆的数量的，如果每小时能吃掉数量最多的香蕉堆的速度来吃香蕉的话，必然能将全部香蕉吃完，所以最小的速度必然在 $[1, max(piles)]$ 之中，使用二分查找，查找出能够吃完香蕉的最小速度即可。

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
  let low = 0
  let high = Math.max(...piles)
  const eat = (speed) => piles.reduce((time, cnt) => time + Math.ceil(cnt / speed), 0)
  while (low < high) {
    const mid = low + ((high - low) >> 1)
    if (eat(mid) > h) {
      low = mid + 1
    } else {
      high = mid
    }
  }
  return low
}

• 时间复杂度：$O(n \, log \, m )$，其中 $n$ 是数组 $\text{piles}$ 的长度，$m$ 是数组 $\text{piles}$ 中的最大值。
• 空间复杂度：$O(1)$