【每日算法Day 85】爱吃香蕉的珂珂
Wallace Xu 2020-08-24 二分查找
# LeetCode 875. 爱吃香蕉的珂珂 (opens new window)
# 题目描述
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
# 示例
输入: piles = [30,11,23,4,20], H = 5
输出: 30
输入: piles = [30,11,23,4,20], H = 6
输出: 23
1
2
3
4
5
2
3
4
5
# 解题思路
吃香蕉的速度最小为1根/小时，最快为所有堆中香蕉数量的最大值，则暴力解法是从1开始向上寻找，首次发现可以在警卫回来前能吃完所有香蕉的速度就是最小速度。
由于查找有上下限并且查找的吃香蕉速度是严格增加的，那么可以使用二分查找进行优化。
public int minEatingSpeed(int[] piles, int H) {
int min = 1, max = Integer.MIN_VALUE;
for (int pile : piles)
max = Math.max(max, pile);
while (min <= max) {
int mid = min + ((max - min) >> 1);
if (canFinish(piles, H, mid)) {
max = mid - 1;
} else {
min = mid + 1;
}
}
return min;
}
private boolean canFinish(int[] piles, int H, int speed) {
int hour = 0;
for (int pile : piles)
hour += Math.ceil((double) pile / speed);
return hour <= H;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
该算法的时间复杂度为O(nlogk)，n是香蕉堆数，k为最大堆的香蕉数。