求解思路
这道题我们可以把速度的范围确定在1到最大堆的香蕉数量之间,因为速度最小是1(总得吃),最大也不需要超过最大堆的数量(再快也没意义)。
然后我们在这个范围内不断尝试中间值,对于每个速度计算需要多少小时吃完,
如果小于等于h小时说明这个速度可行,但我们要找最小的,所以继续往左半边找更小的速度;
如果超过h小时说明速度太慢了,就往右半边找更快的速度。
这样不断缩小范围,最终就能找到刚好满足条件的最小速度。
代码解析
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
34
35
36
|
public static int minEatingSpeed(int[] piles, int h) {
// 确定速度的搜索范围[l,r]
int l = 1; // 最小速度为1
int r = 0;
for (int pile : piles) {
r = Math.max(r, pile); // 最大速度为最大堆的数量
}
// 在[l,r]区间内二分查找
int ans = 0;
int m = 0;
while (l <= r) {
m = l + ((r - l) >> 1); // 计算中间速度,避免溢出
if (f(piles, m) <= h) {
// 当前速度可以在h小时内吃完
ans = m; // 记录答案
r = m - 1; // 尝试更小的速度
} else {
// 当前速度太慢,需要更快
l = m + 1;
}
}
return ans;
}
// 计算以speed速度吃完所有香蕉需要的小时数
public static long f(int[] piles, int speed) {
long ans = 0;
for (int pile : piles) {
// 向上取整:(pile + speed - 1) / speed
// 例如:pile=11,speed=4 → (11+3)/4=3小时
ans += (pile + speed - 1) / speed;
}
return ans;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~