05 August 2008
Binary Search
时间复杂度：O(NlogW)，其中 N 是香蕉堆的数量，W 最大的香蕉堆的大小。
空间复杂度：O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int lo = 1;
int hi = 1_000_000_000;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (!possible(piles, H, mi))
lo = mi + 1;
else
hi = mi;
}
return lo;
}
// Can Koko eat all bananas in H hours with eating speed K?
public boolean possible(int[] piles, int H, int K) {
int time = 0;
for (int p: piles)
time += (p-1) / K + 1;
return time <= H;
}
}