博客

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

lefti 是第 i 座建筑物左边缘的 x 坐标。

righti 是第 i 座建筑物右边缘的 x 坐标。

heighti 是第 i 座建筑物的高度。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

class Solution {
    private int[] tree;
    private boolean[] flag;
    public List<List<Integer>> getSkyline(int[][] buildings) {
        // 进行离散化，以Rank值来更新线段树,需要去重
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < buildings.length ; i++) {
            set.add(buildings[i][0]);
            set.add(buildings[i][1]);
        }
        int[] tmp = new int[set.size()];
        int idx = 0;
        for(int t : set){
            tmp[idx++] = t;
        }
        tree = new int[idx << 2];
        flag = new boolean[idx << 2];
        for (int i = 0; i < buildings.length; i++) {
            // 离散化后，以Rank值为基准，而不是x坐标
            int l = Arrays.binarySearch(tmp, buildings[i][0]);
            // 针对第二高的情况特殊处理，Rank值-1和x坐标-1的情况结果都是一样的
            int r = Arrays.binarySearch(tmp, buildings[i][1]) - 1;
            // 进行区间更新，并维护最大值
            update(l, r, buildings[i][2], 0, idx - 1, 1);
        }
        query(0, idx - 1, 1, tmp);
        return ans;
    }
    // 将懒惰标记延迟到子树
    public void pushDown(int rt){
        // 懒惰标记更新到子树后去除标记，不需要再进行延迟
        if (flag[rt]){
            tree[rt << 1] = Math.max(tree[rt << 1], tree[rt]);
            tree[rt << 1 | 1] = Math.max(tree[rt << 1 | 1], tree[rt]);
            flag[rt << 1] = true;
            flag[rt << 1 | 1] = true;
            flag[rt] = !flag[rt];
        }
    }
    // 区间更新，并维护区间的最大值
    private void update(int L, int R, int max, int l, int r, int rt){
        if (tree[rt] >= max){
            return;
        }
        if (l >= L && r <= R){
            tree[rt] = max;
            flag[rt] = true;
            return;
        }
        // 需要将懒惰标记更新到子树
        pushDown(rt);
        int mid = (l + r) >> 1;
        if (L <= mid){
            update(L, R, max, l, mid, rt << 1);
        }
        if (R > mid){
            update(L, R, max,mid + 1, r, rt << 1 | 1);
        }
    }
    // 维护上一条扫描线的关键点的值
    private int last = 0;
    private List<List<Integer>> ans = new ArrayList<>();
    // 查询每个叶子节点的最大值
    private void query(int l, int r, int rt, int[] tmp){
        if (l == r){
            // 若当前叶子节点和上一个叶子节点的值相同，说明这两个叶子节点属于同一个矩形，则不是关键点
            // bb的情况
            if (tree[rt] != last){
                last = tree[rt];
                ans.add(Arrays.asList(tmp[l], tree[rt]));
            }
            // ba的情况下直接认为该关键点无效
            return;
        }
        pushDown(rt);
        int mid = (l + r) >> 1;
        query(l, mid, rt << 1, tmp);
        query(mid + 1, r, rt << 1 | 1, tmp);
    }
}