875. 爱吃香蕉的珂珂

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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.

Example 1:

Input: piles = [3,6,7,11], h = 8

Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5

Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6

Output: 23

Constraints:

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

题目大意

珂珂喜欢吃香蕉。这里有 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 <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

解题思路

我们可以利用 二分查找 来解决问题。

1. 定义二分查找范围：

• 最小速度 k 为 1（即每小时至少吃 1 个香蕉）。
• 最大速度 k 为 max(piles)（如果珂珂每小时能吃光一堆香蕉，则速度不需要更快）。

2. 设计判定条件：

• 给定吃香蕉速度 k，我们计算吃完所有香蕉所需的总时间：
  • 遍历所有香蕉堆，对于每堆的香蕉数 pile，需要的时间为 ceil(pile / k)（整数除法的向上取整）。
• 如果所需总时间小于或等于 h，则 k 是可行的吃香蕉速度。

3. 二分查找：

• 在范围 [1, max(piles)] 中进行二分查找：
  • 如果速度 k 可行（即在 h 小时内能吃完），尝试减小速度（右边界缩小）。
  • 如果速度 k 不可行，尝试增大速度（左边界增大）。
• 最终找到的左边界即为最小的可行速度。

复杂度分析

• 时间复杂度：O(n * log(max(piles)))
  • 二分查找的次数为 O(log(max(piles))) 。
  • 每次判定需要遍历 piles 数组，时间复杂度为 O(n) 。
  • 总时间复杂度为 O(n * log(max(piles))) 。
• 空间复杂度：O(1)，使用了常数额外空间。

代码

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
	// 二分查找范围
	let left = 1,
		right = Math.max(...piles);

	// 定义计算需要时间的函数
	const canFinish = (speed) => {
		let time = 0;
		for (let pile of piles) {
			time += Math.ceil(pile / speed); // 计算吃完每堆所需时间
		}
		return time <= h; // 是否在 h 小时内完成
	};

	// 二分查找
	while (left < right) {
		const mid = Math.floor((left + right) / 2);
		if (canFinish(mid)) {
			right = mid; // 尝试更小的速度
		} else {
			left = mid + 1; // 增大速度
		}
	}

	return left; // 最小的速度
};

相关题目

题号	标题	题解	标签	难度	力扣
774	最小化去加油站的最大距离 🔒		数组 二分查找	🔴	🀄️ 🔗
2064	分配给商店的最多商品的最小值	[✓]	数组 二分查找	🟠	🀄️ 🔗
2226	每个小孩最多能分到多少糖果		数组 二分查找	🟠	🀄️ 🔗
2498	青蛙过河 II		贪心 数组 二分查找	🟠	🀄️ 🔗
2594	修车的最少时间		数组 二分查找	🟠	🀄️ 🔗