四刷
38.16 %
class Solution {
public List<int[]> getSkyline(int[][] buildings) {
// check if the highest hight has changed or not
// int[] 0-represents the x, 0-represents height, minus if it is the end
List<int[]> heights = new ArrayList<>();
for (int[] building : buildings) {
// building[0] -> start
// building[1] -> end
// building[2] -> height
heights.add(new int[]{building[0], building[2]});
heights.add(new int[]{building[1], -building[2]});
}
// compare by x
// if 1 end and 1 start, start should come before end
// if both start, heigher one should come first
// if both end, lower one should come first
Collections.sort(heights, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return b[1] - a[1];
});
// all the points that are under consideration
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(0);
List<int[]> result = new ArrayList<>();
int currHeight = 0;
for (int[] height : heights) {
if (height[1] > 0) {
maxHeap.offer(height[1]);
} else {
maxHeap.remove(-height[1]);
}
if (maxHeap.peek() != currHeight) {
currHeight = maxHeap.peek();
result.add(new int[]{height[0], currHeight});
}
}
return result;
}
}
[3rd TRY]
1 bug -> should have checked if pq is empty before do pq.peek()
51.67 %
class Solution {
class Point {
int x;
int height;
int isEnd; // 0 for start, 1 for end
public Point(int x, int height, int isEnd) {
this.x = x;
this.height = height;
this.isEnd = isEnd;
}
}
public List<int[]> getSkyline(int[][] buildings) {
// we keep a list of heights -> if the highest point changes, then it should be added to skyline
// sort by their x positions, we need to know either it is a start point or a end point
// 4 kinds of ties
// if a ends and b starts, a < b, then we want to add b first and then remove a -> start 0, end 1
// if a ends and b starts, a > b, same
// if a,b ends at the same time, then we want to remove the lower one first
// if a,b stars at the same time, then we want to add the higher one first
List<Point> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new Point(building[0], building[2], 0));
list.add(new Point(building[1], building[2], 1));
}
Collections.sort(list, (a, b) -> {
if (a.x != b.x) {
return a.x - b.x;
}
if (a.isEnd != b.isEnd) {
return a.isEnd - b.isEnd; // Always return the start one first
} else if (a.isEnd == 0) {
return b.height - a.height;
} else {
return a.height - b.height;
}
});
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(16, Collections.reverseOrder());
int prevHeight = 0;
List<int[]> result = new ArrayList<>();
for (Point curr : list) {
if (curr.isEnd == 0) { // isStart
maxHeap.add(curr.height);
} else {
maxHeap.remove(curr.height);
}
int currHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek();
if (currHeight != prevHeight) {
prevHeight = currHeight;
result.add(new int[]{curr.x, currHeight});
}
}
return result;
}
}
二刷
Time O(n^2) -> linear time to remove
Space O(n)
class Solution {
// int[0] -> x, int[1] -> height, int[2] -> 0 start, 1 end
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) {
return result;
}
// buildings[i][0] -> start, buildings[i][1] -> end, buildings[i][2] -> height
List<int[]> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new int[]{building[0], building[2], 0});
list.add(new int[]{building[1], building[2], 1});
}
Collections.sort(list, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else if (a[2] != b[2]) {
// start before end
return a[2] - b[2];
} else if (a[2] == 0) {
// Two start, add the higher one first
return b[1] - a[1];
} else {
// Two end, remove the lower one first
return a[1] - b[1];
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
int currHeight = 0;
int[] curr = null;
for (int i = 0; i < list.size(); i++) {
curr = list.get(i);
if (curr[2] == 0) {
pq.add(curr[1]);
} else {
pq.remove(curr[1]);
}
if (pq.isEmpty()) {
result.add(new int[]{curr[0], 0});
currHeight = 0;
} else if (currHeight != pq.peek()){
result.add(new int[]{curr[0], pq.peek()});
currHeight = pq.peek();
}
}
return result;
}
}
一刷
Input:[[0,2,3],[2,5,3]]
Output:[[0,3],[2,3],[5,0]]
Expected:[[0,3],[5,0]]
有四种breaking tie的情况，决定了sort的顺序上面的一个bug要注意如果second largest和之前pop出去的一样高，就不往结果里面加
还有一个是PriorityQueue remove(Object)
是remove single one
59.53 %
class Solution {
class Tuple {
int pos;
int height;
int isEnd; // 0 -> isStart, 1 -> isEnd
public Tuple(int pos, int height, int isEnd) {
this.pos = pos;
this.height = height;
this.isEnd = isEnd;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) return result;
List<Tuple> tuples = new ArrayList<>();
for (int[] building : buildings) {
// 0 1 2
// [Li, Ri, Hi]
tuples.add(new Tuple(building[0], building[2], 0));
tuples.add(new Tuple(building[1], building[2], 1));
}
// maxHeap
PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
Collections.sort(tuples, new Comparator<Tuple>() {
@Override
public int compare(Tuple t1, Tuple t2) {
if (t1.pos != t2.pos) {
return t1.pos - t2.pos;
} else if (t1.isEnd != t2.isEnd) {
// start(0) befor end(1)
return t1.isEnd - t2.isEnd;
} else if (t1.isEnd == 0) {
// if both start, higher before lower
return t2.height - t1.height;
} else {
// if both end, lower before higher
return t1.height - t2.height;
}
}
});
// output [x1,y1] -> [pos, height]
for (int i = 0; i < tuples.size(); i++) {
Tuple curr = tuples.get(i);
// start -> add
if (curr.isEnd == 0) {
if (pq.isEmpty() || curr.height > pq.peek()) {
result.add(new int[]{curr.pos, curr.height});
}
pq.add(curr.height);
} else { // end -> delete
if (pq.peek() == curr.height) {
pq.poll();
if (pq.isEmpty()) {
result.add(new int[]{curr.pos, 0});
} else if (pq.peek() != curr.height){
result.add(new int[]{curr.pos, pq.peek()});
}
} else {
pq.remove(new Integer(curr.height));
}
}
}
return result;
}
}
No comments:
Post a Comment