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
| class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = piles[0];
for (int i = 1; i < piles.length; i++) {
right = Math.max(right, piles[i]);
}
int ans = right;
while (left <= right) {
int mid = left + (right - left) / 2;
long count = 0;
for (int pile : piles) {
count += pile / mid;
count += pile % mid == 0 ? 0 : 1;
}
if (count <= h) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
|
Binary Search.
最大的速度就是piles里面的最大值, 这能保证每一个pile都是1小时搞定, 最小的速度就是1. 然后就binary search就完事儿了.
需要注意的是count需要声明为long类型, 否则可能会overflow.
当然可以用Math.ceil()这个method, 我们给定一个double类型的数字, 它能告诉我们比该数字大的数字中最小的整数double是多少. 和它相对应的还有Math.floor(), 我们同样给定一个double数字, 它能告诉我们比该数字小的数字中最大的整数double是多少.
时间复杂度: O(nlogm) n是piles的长度, m是piles中的最大值. 因为我们每次都要遍历piles中的每个数字, 一共遍历logm次.
空间复杂度: O(1)
