- 作者:老汪软件技巧
- 发表时间:2024-09-29 04:00
- 浏览量:
难度:中等;
题目:
珂珂喜欢吃香蕉。这里有 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
提示:
解题思路:
这道题目是一个典型的二分查找问题,不过它不是在有序数组中查找特定元素,而是要找到满足一定条件下的最小速度。问题的关键在于,速度 k 必须足够快,以至于在给定的时间 h 内吃完所有香蕉,但又要尽可能地慢,以确保 k 是满足条件的最小整数值。
确定边界:最小速度显然是 1(根/小时),而最大速度则至少是所有堆中香蕉数量的最大值(因为如果速度低于任何一堆香蕉的数量,就不能在一小时内吃完那一堆)。所以,我们设置二分查找的边界为 low = 1 和 high = Math.max(...piles)。二分查找:在 low 和 high 之间进行二分查找,寻找满足条件的最小速度。每次取中间值 mid 作为当前速度,然后计算在该速度下吃完所有香蕉所需的总时间。如果总时间小于等于 h,则说明当前速度过快,我们可以在 [low, mid - 1] 范围内继续查找更慢的速度;否则,说明速度过慢,我们需要在 [mid + 1, high] 范围内查找更快的速度。计算时间:为了计算在给定速度 k 下吃完所有香蕉所需的总时间,对于每堆香蕉,我们需要向上取整除以速度 k 来得到吃完该堆香蕉所需的时间。这是因为如果香蕉数量不能被速度整除,意味着吃完这堆香蕉需要花费额外的一小时。返回结果:当 low 和 high 相遇时,二分查找结束,此时的 low(或 high)就是满足条件的最小速度。JavaScript代码实现:
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
var minEatingSpeed = function(piles, h) {
let low = 1;
let high = Math.max(...piles);
while (low < high) {
let mid = Math.floor((low + high) / 2);
let hoursNeeded = 0;
for (let pile of piles) {
hoursNeeded += Math.ceil(pile / mid);
}
if (hoursNeeded <= h) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
};
// 示例调用
// console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 输出: 4
// console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 输出: 30