leetcode-875 爱吃香蕉的珂珂

题目描述:珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int len = piles.length;
int maxSpeed = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
if (piles[i] > maxSpeed) {
maxSpeed = piles[i];
}
}
int left = 1;
int right = maxSpeed + 1;
while (left < right) {
int mid = left + (right - left) / 2;
int hour = calculateHour(piles, mid);
if (hour == h) {
right = mid;
} else if (hour < h) {
right = mid;
} else if (hour > h) {
left = mid + 1;
}
}
return left;
}

public int calculateHour(int[] piles, int speed) {
int hours = 0;
for (int i = 0; i < piles.length; i++) {
hours += (piles[i] / speed + (piles[i] % speed != 0 ? 1 : 0));
}
return hours;
}
}