题目
珂珂喜欢吃香蕉。这里有 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^4piles.length <= h <= 10^91 <= piles[i] <= 10^9
解题
方法一：二分查找
思路
如果珂珂在 小时内吃掉所有香蕉的最小速度是每小时 个香蕉，则当吃香蕉的速度大于每小时 个香蕉时一定可以在 小时内吃掉所有香蕉，当吃香蕉的速度小于每小时 个香蕉时一定不能在 小时内吃掉所有香蕉。
由于吃香蕉的速度和是否可以在规定时间内吃掉所有香蕉之间存在单调性，因此可以使用二分查找的方法得到最小速度 。
由于每小时都要吃香蕉，即每小时至少吃 个香蕉，因此二分查找的下界是 ；由于每小时最多吃一堆香蕉，即每小时吃的香蕉数目不会超过最多的一堆中的香蕉数目，因此二分查找的上界是最多的一堆中的香蕉数目。
问题转换为找到小于等于$ h$ 的值的下标。采用「小于等于」情形的写法。需要注意的是，用于与 做比较的 ，需要在每一次得到一个新 (med) 值后以一次遍历求出， 说明耗时较 多，需要加快速度，于是 min = med + 1。min 的左侧为耗时多于 h 的速度，因此最终返回 min。
代码
class Solution {
private int[] piles;
public int minEatingSpeed(int[] _piles, int h) {
piles = _piles;
int min = 1, max = 0;
for (int pile : piles) max = Math.max(max, pile);
while (min <= max) {
int med = min + ((max - min) >> 1);
if (spent(med) > h) min = med + 1;
else max = med - 1;
}
return min;
}
private int spent(int k) {
int time = 0;
for (int pile : piles) {
time += pile / k;
if (pile % k != 0) time++;
}
return time;
}
}
模板1
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l = 1, r = 0;
for (int pile : piles) r = Math.max(r, pile);
while (l < r) {
int mid = l + (r - l >> 1);
if (check(piles, h, mid)) r = mid;
else l = mid + 1;
}
return l;
}
boolean check(int[] nums, int x, int mid) {
int hour = 0;
for (int num : nums) {
hour += (num + mid - 1) / mid;
if (hour > x) return false;
}
return true;
}
}
模板2
1、确定 x, f(x), target 分别是什么，并写出函数 f 的代码。
自变量 x 是什么呢？回忆之前的函数图像，二分搜索的本质就是在搜索自变量。
所以，题目让求什么，就把什么设为自变量，珂珂吃香蕉的速度就是自变量 x。
那么，在 x 上单调的函数关系 f(x) 是什么？
显然，吃香蕉的速度越快，吃完所有香蕉堆所需的时间就越少，速度和时间就是一个单调函数关系。
所以，f(x) 函数就可以这样定义：
若吃香蕉的速度为 x 根/小时，则需要 f(x) 小时吃完所有香蕉。
代码实现如下：
// 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉
// f(x) 随着 x 的增加单调递减
int f(int[] piles, int x) {
int hours = 0;
for (int i = 0; i < piles.length; i++) {
hours += piles[i] / x;
if (piles[i] % x > 0) {
hours++;
}
}
return hours;
}
target 就很明显了，吃香蕉的时间限制 H 自然就是 target，是对 f(x) 返回值的最大约束。
2、找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。
珂珂吃香蕉的速度最小是多少？多大是多少？
显然，最小速度应该是 1，最大速度是 piles 数组中元素的最大值，因为每小时最多吃一堆香蕉，胃口再大也白搭嘛。
这里可以有两种选择，要么你用一个 for 循环去遍历 piles 数组，计算最大值，要么你看题目给的约束，piles 中的元素取值范围是多少，然后给 right 初始化一个取值范围之外的值。
我选择第二种，题目说了 1 <= piles[i] <= 10^9，那么我就可以确定二分搜索的区间边界：
public int minEatingSpeed(int[] piles, int H) {
int left = 1;
// 注意，right 是开区间，所以再加一
int right = 1000000000 + 1;
// ...
}
3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。
现在我们确定了自变量 x 是吃香蕉的速度，f(x) 是单调递减的函数，target 就是吃香蕉的时间限制 H，题目要我们计算最小速度，也就是 x 要尽可能小：
这就是搜索左侧边界的二分搜索嘛，不过注意 f(x) 是单调递减的，不要闭眼睛套框架，需要结合上图进行思考，写出代码：
public int minEatingSpeed(int[] piles, int H) {
int left = 1;
int right = 1000000000 + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (f(piles, mid) == H) {
// 搜索左侧边界，则需要收缩右侧边界
right = mid;
} else if (f(piles, mid) < H) {
// 需要让 f(x) 的返回值大一些
right = mid;
} else if (f(piles, mid) > H) {
// 需要让 f(x) 的返回值小一些
left = mid + 1;
}
}
return left;
}
PS：关于
mid是否需要 + 1 的问题，前文 二分搜索算法详解 进行了详细分析，这里不展开了。
class Solution {
int f(vector<int>& piles, int k) {
int hour = 0;
for (int& pile : piles) hour += (pile + k - 1) / k;
return hour;
}
public:
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1, right = 0;
for (int& pile : piles) right = max(right, pile);
while (left < right) {
int mid = left + ((right - left) >> 1);
if (f(piles, mid) <= h) right = mid;
else left = mid + 1;
}
return left;
}
};
评论区