Leetcode: 218. 天际线问题

题目描述

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi 是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

说明:

任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
输入列表已经按左 x 坐标 Li  进行升序排列。
输出列表必须按 x 位排序。
输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

思路

思路1

使用分治法，类似与插入排序思路。重点在于看到单个建筑物的应该如何存储。如[1, 5, 9]存为[1, 9],[5, 0],即分好左右节点.参考

思路2

使用最大优先级队列保存最高点，然后根据左右节点以类似入栈出栈形式得到结果。关键在于存储左右节点

思路3

可以使用TreeMap使得时间复杂度为$O(nlogn)$思路

代码

代码1

class Solution {
    public List> getSkyline(int[][] buildings) {
        List> result = new ArrayList<>();
        int n = buildings.length;
        
        if (n == 0){return result;}
        if (n == 1){
            result.add(new ArrayList() {{add(buildings[0][0]); add(buildings[0][2]);}});
            result.add(new ArrayList() {{add(buildings[0][1]); add(0);}});
            return result;
        }
        
        List> left, right;
        left = getSkyline(Arrays.copyOfRange(buildings,0, n / 2));
        right = getSkyline(Arrays.copyOfRange(buildings, n/2, n));
        
        return mergeResult(left, right);
    }
    
    private List> mergeResult(List> left, List> right){
        int ls = 0, rs = 0;
        int le = left.size(), re = right.size();
        int leftY = 0, rightY = 0, curY = 0;
        int x, maxY;
        List> result = new ArrayList<>();
        
        while (ls < le && rs < re){
            List leftP = left.get(ls);
            List rightP = right.get(rs);
            
            if (leftP.get(0) < rightP.get(0)){
                x = leftP.get(0);
                ls ++;
                leftY = leftP.get(1);
            }else{
                x = rightP.get(0);
                rs ++;
                rightY = rightP.get(1);
            }
            maxY = Math.max(leftY, rightY);
            if (curY != maxY){
                updateResult(result, x, maxY);
                curY = maxY;
            }
        }
        
        addRest(result, left, ls, le, curY);
        addRest(result, right, rs, re, curY);
        return result;  
    }
    
    private void updateResult(List> result, int x, int y){
        if (result.isEmpty() || result.get(result.size() - 1).get(0) != x){
            result.add(new ArrayList(){{add(x); add(y);}});
        }else{
            result.get(result.size() - 1).set(1, y);
        }
    }
    
    private void addRest(List> result, List> left, int s, int e, int curY){
        while (s < e){
            List point = left.get(s);
            int x = point.get(0);
            int y = point.get(1);
            s ++;
            
            if (y != curY){
                updateResult(result, x, y);
                curY = y;
            }
        }
    }
    
}

代码2

class Solution {
    public List> getSkyline(int[][] buildings) {
        List> result = new ArrayList<>();
        if (buildings.length == 0){
            return result;
        }
        List> marks = new ArrayList<>();
        for(int[] nums: buildings){
            marks.add(new ArrayList(){{add(nums[0]);add(-nums[2]);}});
            marks.add(new ArrayList(){{add(nums[1]); add(nums[2]);}});
        }
        
        Collections.sort(marks, new Comparator>(){
            @Override
            public int compare(List o1, List o2){
                int x1 = o1.get(0);
                int x2 = o2.get(0);
                int y1 = o1.get(1);
                int y2 = o2.get(1);
                if (x1 != x2){
                    return x1 - x2;
                }else{
                    return y1 - y2;
                }
            }
        });
        
        Queue queue = new PriorityQueue(new Comparator(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        queue.offer(0);
        int preY = 0;
        for(List nums: marks){
            int x = nums.get(0);
            int y = nums.get(1);
            
            if (y < 0){
                queue.offer(-y);
            }else{
                queue.remove(y);
            }
            int curMax = queue.peek();
            if (preY != curMax){
                result.add(new ArrayList(){{add(x); add(curMax);}});
                preY = curMax;
            }
        }
        return result;
    }
}