一刷 06/2022
Version #1 Min Heap - conditionally adding new elements
Time O(NlogL) ~ O(NlogN) in the worst case -> N is the length of buildings, L is number of ladders
Space O(L) ~ O(N) in the worst case
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
// Ensure that ladders are used on the longest climbs
// If we're out of ladders, we'll replace the most wasteful ladder allocation with bricks
// min heap is used to store height diff of ladders
Queue<Integer> minHeap = new PriorityQueue<>();
int index = 0;
for (index = 1; index < heights.length; index++) {
int diff = heights[index] - heights[index - 1];
if (diff <= 0) {
continue;
}
if (ladders > 0) {
minHeap.offer(diff);
ladders--;
continue;
}
// ladders == 0, we want to use bricks to replace ladders
int min = diff;
if (!minHeap.isEmpty() && minHeap.peek() < min) {
min = minHeap.poll();
minHeap.offer(diff);
}
// System.out.printf("index=%d, min=%d, bricks=%d\n", index, min, bricks);
if (bricks < min) {
return index - 1;
}
bricks -= min;
}
return heights.length - 1;
}
}
Version #2 Max Heap - shorter version
Time O(NlogN) - N number of buildings
Space O(N)
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
// Use bricks for the shortest climbs
Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
int index = 0;
for (index = 1; index < heights.length; index++) {
int diff = heights[index] - heights[index - 1];
if (diff <= 0) {
continue;
}
maxHeap.offer(diff);
bricks -= diff;
if (bricks >= 0) {
continue;
}
bricks += maxHeap.poll();
if (ladders > 0) {
ladders--;
} else {
return index - 1;
}
}
return heights.length - 1;
}
}
Version #3 Binary Search
Binary Search的思路其实是比较好想的，难点在于怎么不重复地sort [0, mid]之间的height difference
如果不优化的话，每一次canReach都需要NlogN的时间，总体就是O(N(logN)^2)的复杂度
这个方法的巧思在于把整个的height difference和它们的index一起sort，如果index不在范围就跳过
Time O(NlogN)
Space O(N)
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
// Globally sort the difference of heights
List<List<Integer>> diffs = new ArrayList<>();
for (int i = 1; i < heights.length; i++) {
int diff = heights[i] - heights[i - 1];
if (diff > 0) {
diffs.add(Arrays.asList(new Integer[]{diff, i}));
}
}
Collections.sort(diffs, (a, b) -> a.get(0) - b.get(0));
int start = 0, end = heights.length - 1;
// Find the last index that can reach
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (canReach(mid, diffs, bricks, ladders)) {
start = mid;
} else {
end = mid - 1;
}
}
if (canReach(end, diffs, bricks, ladders)) {
return end;
}
return start;
}
private boolean canReach(int index, List<List<Integer>> diffs, int bricks, int ladders) {
for (List<Integer> diff : diffs) {
if (diff.get(1) > index) {
continue;
}
if (bricks >= diff.get(0)) {
bricks -= diff.get(0);
} else {
ladders--;
}
}
return ladders >= 0;
}
}
No comments:
Post a Comment