可以用Math.ceil()
Math.ceil((double) pile / middle)
Let n be the length of the input array piles and m be the maximum number of bananas in a single pile from piles.
Time complexity O(nlogm)
Space O(1)
Runtime: 26 ms, faster than 59.51% of Java online submissions for Koko Eating Bananas.
Memory Usage: 54.1 MB, less than 40.11% of Java online submissions for Koko Eating Bananas.
class Solution {
public int minEatingSpeed(int[] piles, int h) {
if (piles == null) {
throw new IllegalArgumentException();
}
int start = 1, end = 1;
for (int pile : piles) {
end = Math.max(end, pile);
}
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (canFinish(piles, h, mid)) {
end = mid;
} else {
start = mid + 1;
}
}
if (canFinish(piles, h, start)) {
return start;
}
return end;
}
private boolean canFinish(int[] piles, int h, int speed) {
for (int pile : piles) {
h -= (pile / speed + (pile % speed == 0 ? 0 : 1));
}
return h >= 0;
}
}
一刷
69.22 %
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int sum = 0;
int max = Integer.MIN_VALUE;
for (int pile : piles) {
sum += pile;
max = Math.max(max, pile);
}
int start = Math.max(1, sum / H);
int end = max;
// find the first speed that can finish
while (start < end) {
int mid = start + (end - start) / 2;
if (canFinish(mid, piles, H)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
private boolean canFinish(int k, int[] piles, int H) {
for (int pile : piles) {
if (pile <= k) {
H--;
} else {
H -= pile / k + (pile % k == 0 ? 0 : 1);
}
if (H < 0) break;
}
return H >= 0;
}
}
No comments:
Post a Comment