题目描述
这是 LeetCode 上的 「875. 爱吃香蕉的珂珂」 ，难度为 「中等」。
Tag : 「二分」
珂珂喜欢吃香蕉。这里有 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
提示：
二分
由于存在「吃完这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉」的条件，因此不会存在多堆香蕉共用一个小时的情况，即每堆香蕉都是相互独立，同时可以明确每堆香蕉的耗时为
因此我们可以二分
-
小于 -
大于等于
然后我们需要确定二分的范围，每堆香蕉至少消耗一个小时，因此大于
piles 进行一次遍历，找最大值，再二分；也可以直接利用数据范围
最后的 check 函数，只需要计算当前速率
代码：
class?Solution?{
????public?int?minEatingSpeed(int[]?piles,?int?h)?{
????????int?l?=?0,?r?=?(int)1e9;
????????while?(l?<?r)?{
????????????int?mid?=?l?+?r?>>?1;
????????????if?(check(piles,?mid,?h))?r?=?mid;
????????????else?l?=?mid?+?1;
????????}
????????return?r;
????}
????boolean?check(int[]?p,?int?k,?int?h)?{
????????int?ans?=?0;
????????for?(int?x?:?p)?ans?+=?Math.ceil(x?*?1.0?/?k);
????????return?ans?<=?h;
????}
}
-
时间复杂度：令 -
空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.875 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本文由 mdnice 多平台发布