暴力查找
解题思路
珂珂吃的速度和时间是此消彼长的关系，吃的速度越快，花的时间越少，吃的速度越慢，花的时间越多；要让珂珂吃得够慢，又能吃完；
那从最最慢开始，让珂珂一小时只吃 1 个（k = 1），看珂珂能否在 h 小时内吃完，如果吃不完，就吃 2 个(k++)，重头吃一遍，一直到找到 k；
这种暴力迭代的方式会超时，但是很有用，直接上二分会让人不理解；
复杂度
-
时间复杂度：
O(k)，其中 k 是珂珂吃的速度，从 1 到 k 次的循环； -
空间复杂度：
O(1)
代码实现
var minEatingSpeed = function (piles, h) {
// 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
let k = 1;
while (true) {
if (canFinish(k, h, piles)) {
return k; // 可以吃完，返回 k
}
k++; // 当不能吃完的时候，多吃一根再试试
}
}
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
let totalTime = 0;
for (var i = 0; i < piles.length; i++) {
// 当香蕉少于 k 的时候，当成 1 小时算
totalTime += Math.ceil(piles[i] / k);
// 已经超时了？那就直接返回吃不完，不再继续吃
if (totalTime > h) {
return false;
}
}
return true; // 可以吃完
}
二分查找
解题思路
可以从上面的 暴力迭代 的方式中发现，k 从 1 开始遍历效率太低了，而且会超时；
有没有别的方式呢？ 既然 k 最小是 1 ，最大是多少呢？ 根据题意 每个小时，她将会选择一堆香蕉，从中吃掉 k 根，如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉 ，那么 k 最大是最多的那一堆香蕉数量；
也就是要在一个范围里找 k ，这个范围还是单调递增的序列，这就很容易的联想到了 二分查找；
复杂度
-
时间复杂度：
O(nlogm)，其中 n 是数组 piles 的长度，需要O(n)的时间遍历数组找到最大值 m；二分查找需要执行O(logm)轮 -
空间复杂度：
O(1)
代码实现
var minEatingSpeed = function (piles, h) {
let left = 1;
let right = Math.max(...piles);
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (canFinish(mid, h, piles)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
let totalTime = 0;
for (var i = 0; i < piles.length; i++) {
// 当香蕉少于 k 的时候，当成 1 小时算
totalTime += Math.ceil(piles[i] / k);
// 已经超时了？那就直接返回吃不完，不再继续吃
if (totalTime > h) {
return false;
}
}
return true; // 可以吃完
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1300. 转变数组后最接近目标值的数组和
上一篇
评论
