JZTXT

【扫描线】LeetCode 218. 天际线问题

发布时间 2023-04-13 10:39:28作者: Frodo1124

题目链接

218. 天际线问题

思路

参考宫水三叶大佬题解

代码

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList<>();
        List<int[]> path = new ArrayList<>();

        for(int[] building : buildings){
            int left = building[0];
            int right = building[1];
            int height = building[2];

            // 方便排序,让左端点高度为负数;同时能识别当前点为左端点还是右端点
            path.add(new int[]{left, -height});
            path.add(new int[]{right, height});
        }

        Collections.sort(path, (a, b) -> {
            if(a[0] != b[0]){
                return a[0] - b[0];
            }

            return a[1] - b[1];
        });

        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        int prev = 0;
        queue.add(prev);

        for(int i = 0; i < path.size(); i++){
            int[] temp = path.get(i);
            if(temp[1] < 0){
                queue.add(-temp[1]);
            }else{
                queue.remove(temp[1]);
            }

            int current = queue.peek();
            if(current != prev){
                prev = current;
                result.add(Arrays.asList(new Integer[]{temp[0], current}));
            }
        }

        return result;
    }
}