用line sweep
输入(x1,x2,y),左上角顶点用(x1,-y)表示,右上角顶点用(x2,y)表示
如示例,输入:
[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]
及每个转折点为:
[2,10],[9,10],[3,15],[7,15],[5,12],[12,12],[15,10],[20,10],[19,8],[24,8]
按上述方法表示后并排序,变为:
[2,-10],[3,-15],[5,-12],[7,15],[9,10],[12,12],[15,-10],[19,-8],[20,10],[24,8]
从左至右扫描每一条边缘线,左边缘线计入高度,右边缘线清除高度
如果内部高度发生了变化,说明到了关键点
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> points = new ArrayList<>();
//左上角和右上角坐标
for(int[] b :buildings){
points.add(Arrays.asList(b[0],-b[2]));
points.add(Arrays.asList(b[1],b[2]));
}
//所有坐标排序
points.sort(
(a, b) -> {
int x1 = a.get(0),y1 = a.get(1);
int x2 = b.get(0),y2 = b.get(1);
if(x1 != x2)
return x1 - x2;
else
return y1 - y2;
}
);
Queue<Integer> queue = new PriorityQueue<>((a,b) -> b - a);
queue.offer(0);
int preMax = 0;
List<List<Integer>> res = new ArrayList<>();
for(List<Integer> p : points){
int x = p.get(0),y = p.get(1);
//左上角坐标
if(y < 0)
queue.offer(-y);
//右上角坐标
else
queue.remove(y);
int curMax = queue.peek();
//最大值更新了,加入当前结果
if(curMax != preMax){
res.add(Arrays.asList(x,curMax));
preMax = curMax;
}
}
return res;
}
}