链接

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

每个建筑物的几何信息由数组 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], ...]

import java.util.*;

class Solution {
    public static List<List<Integer>> getSkyline(int[][] buildings) {
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return new ArrayList<>(0);
        }

        int n = buildings.length;

        Operation[] operations = new Operation[n << 1];

        for (int i = 0; i < n; ++i) {
            operations[i << 1] = new Operation(buildings[i][0], true, buildings[i][2]);
            operations[i << 1 | 1] = new Operation(buildings[i][1], false, buildings[i][2]);
        }


        Arrays.sort(operations, new Comparator<Operation>() {
            @Override
            public int compare(Operation o1, Operation o2) {
                return Integer.compare(o1.x, o2.x);
            }
        });

        TreeMap<Integer, Integer> heightTimesMap = new TreeMap<>();
        TreeMap<Integer, Integer> heightMap = new TreeMap<>();

        for (Operation operation : operations) {
            if (operation.add) {
                heightTimesMap.put(operation.height, heightTimesMap.getOrDefault(operation.height, 0) + 1);
            } else {
                if (heightTimesMap.get(operation.height) == 1) {
                    heightTimesMap.remove(operation.height);
                } else {
                    heightTimesMap.put(operation.height, heightTimesMap.get(operation.height) - 1);
                }
            }
            heightMap.put(operation.x, heightTimesMap.isEmpty() ? 0 : heightTimesMap.lastKey());
        }

        int preHeight = 0;
        List<List<Integer>> ret = new ArrayList<>();

        for (Map.Entry<Integer, Integer> entry : heightMap.entrySet()) {
            if (preHeight != entry.getValue()) {
                ret.add(Arrays.asList(entry.getKey(), entry.getValue()));
            }
            preHeight = entry.getValue();
        }


        return ret;
    }
}

class Operation {
    int x;
    boolean add;
    int height;

    public Operation(int x, boolean add, int height) {
        this.x = x;
        this.add = add;
        this.height = height;
    }
}