算法-珂珂吃香蕉问题

leetcode 875：爱吃香蕉的珂珂 https://leetcode-cn.com/problems/koko-eating-bananas/
可以看看我的题解：https://leetcode.cn/problems/koko-eating-bananas/solutions/1094146/bu-yao-shang-lai-jiu-gao-su-wo-shi-er-fe-8n1y/

题目

珂珂喜欢吃香蕉。这里有  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. 珂珂要吃香蕉，面前摆了 n 堆，一堆一堆地吃；
2. 珂珂 1 小时能吃 k 个；但如果一堆少于 k 个，那也得花一小时 (一小时到了，才吃下一堆)
3. 如果 1 堆大于 k 个，那么超过 k 的部分也算 1 小时。（例如，一堆 10 个，k=3 时，珂珂花 3 小时吃了 9 个，剩下的 1 个也算 1 小时，也就是总用时 4 小时）
4. 问：只给 h 小时，珂珂要吃多慢(k 多小)，才能充分占用这 h 小时

思路

珂珂吃的速度和时间是此消彼长的关系，吃的速度越快，花的时间越少。吃的速度越慢，花的时间越多。

我们要让珂珂吃得够慢，又能吃完。

那我们从最最慢开始，让珂珂一小时只吃 1 个（k=1），看珂珂能否在 h 小时内吃完。

如果吃不完，就吃 2 个(k+1)，重头吃一遍。

一直到找到 k。

说到这里，就可以写出推断的代码了。（那怎么判断吃不吃得完? 这么想：它就是一个函数，吃得完返回 true，吃不完返回 false，具体实现可以后面再做）

var minEatingSpeed = function(piles, h) {
    // 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
    let k = 1
    // 一直试吃
    while(true) {
        // 可以吃完，返回 k
        if(canFinish(...)) {
            return k
        }
        // 当不能吃完的时候，多吃一根再试试
        k++
    }
};

接下来问题变成, 怎么判断能否吃完？硬算！

按顺序去吃每一堆，记录时间；最后超过了 h 小时，说明吃不完：

// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
  // 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
  let totalTime = 0
  // 循环每堆
  for (var i = 0; i < piles.length; i++) {
    // 当香蕉少于 k 的时候，当成 1 小时算
    if (piles[i] <= k) {
      totalTime += 1
      // 当香蕉大于 k 的时候，多出的部分按1小时记
    } else {
      totalTime += Math.ceil(piles[i] / k)
    }
    // 已经超时了？那就直接返回吃不完，不再继续吃
    if (totalTime > h) {
      return false
    }
  }
  // 最后吃完了
  return true
}

那第一版代码就完成了：

var minEatingSpeed = function (piles, h) {
  // 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
  let k = 1
  // 一直试吃
  while (true) {
    // 可以吃完，返回 k
    if (canFinish(k, h, piles)) {
      return k
    }
    // 当不能吃完的时候，多吃一根再试试
    k++
  }
}
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
  // 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
  let totalTime = 0
  // 循环每堆
  for (var i = 0; i < piles.length; i++) {
    // 当香蕉少于 k 的时候，当成 1 小时算
    if (piles[i] <= k) {
      totalTime += 1
      // 当香蕉大于 k 的时候，多出的部分按1小时记
    } else {
      totalTime += Math.ceil(piles[i] / k)
    }
    // 已经超时了？那就直接返回吃不完，不再继续吃
    if (totalTime > h) {
      return false
    }
  }
  // 最后吃完了
  return true
}

优化

我们发现，k 从 1 开始遍历，效率太低了。k 最小是 1，最大是最多的那一堆香蕉数量。

也就是，我们要在一个范围里找 k，这个时候，我才想到二分法：

var minEatingSpeed = function (piles, h) {
  let l = 1
  let r = Math.max(...piles)
  let mid
  while (l < r) {
    mid = Math.floor(l + (r - l) / 2)
    if (canFinish(mid, h, piles)) {
      r = mid
    } else {
      l = mid + 1
    }
  }
  return l
}

最后代码

var minEatingSpeed = function (piles, h) {
  let l = 1
  let r = Math.max(...piles)
  let mid
  while (l < r) {
    mid = Math.floor(l + (r - l) / 2)
    if (canFinish(mid, h, piles)) {
      r = mid
    } else {
      l = mid + 1
    }
  }
  return l
}

// 每小时吃 k, 总数 piles, 时间总长 h
// 一个约束条件是，当香蕉少于 k 的时候，当成 1 小时算
function canFinish(k, h, piles) {
  // 循环每堆
  // 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
  let totalTime = 0
  for (var i = 0; i < piles.length; i++) {
    // console.log(p[i],  k)
    // 当香蕉少于 k 的时候，当成 1 小时算
    if (piles[i] <= k) {
      totalTime += 1
    } else {
      totalTime += Math.ceil(piles[i] / k)
    }
    if (totalTime > h) {
      return false
    }
  }
  return true
}

二分法思路很简单，不就是减半减半再减半吗，但难的是边界问题:

1. left < right 还是 left <= right
2. left 等于 mid 还是 mid + 1 ? right 等于 mid 还是 mid - 1 ？
3. 最后返回 mid ? 还是返回 left ? 还是返回 right?

关于二分的边界，这里有一篇文章写的很详细：
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/