题目

https://leetcode-cn.com/problems/the-skyline-problem/

题解

线段树问题，根据左神的思路改编，外加我想到的压缩的 tricks（数字范围太大，实在想不出别的办法了，一开始是直接把过大的数除以某个 scale，但是这样是有损的，无法复原，于是想到了用 map 存压缩前后的映射关系。只要保持压缩前后的数字大小顺序不变，这个压缩就是无损的。）

class Solution {
    public static final int N = 1 << 15; // 2^15=32768，考虑到 buildings.length <= 10^4，压缩后总共不超过2*10^4个横坐标

    public List<List<Integer>> getSkyline(int[][] buildings) {
        SegmentTree segmentTree = new SegmentTree(N);
        // 压缩（编码）
        // 排序，然后映射，因为不超过10000，所以肯定能映射开
        Set<Integer> set = new TreeSet<>();
        for (int[] task : buildings) {
            set.add(task[0]);
            set.add(task[1]);
        }
        Map<Integer, Integer> decodeMap = new HashMap<>();
        Map<Integer, Integer> encodeMap = new HashMap<>();
        int cipher = 0;
        for (int plain : set) {
            cipher += 2; // 用+2而不是+1，目的是留出地面的间隔，避免两个楼挨在一起时，丢失了地面
            decodeMap.put(cipher, plain);
            encodeMap.put(plain, cipher);
        }
        for (int[] task : buildings) {
            task[0] = encodeMap.get(task[0]);
            task[1] = encodeMap.get(task[1]);
        }
        // 更新线段树（核心）
        for (int[] task : buildings) {
            segmentTree.update(task[0], task[1], task[2], 0, N, 1); // 把从task[0]到task[1]的位置更新为task[2]
        }
        segmentTree.flush();
        // 打补丁（之前为了方便下标索引，线段树是从1位置开始构建的，现在要把0位置也考虑进去）
        segmentTree.max[N - 2] = 0;
        segmentTree.max[2 * N - 1] = 0;
        for (int[] task : buildings) {
            if (task[0] == 0) segmentTree.max[N - 1] = Math.max(segmentTree.max[N - 1], task[2]);
        }
        // 构造返回值（遍历所有叶子）
        List<List<Integer>> result = new ArrayList<>();
        for (int i = N - 1; i < 2 * N; i++) {
            if (segmentTree.max[i] != segmentTree.max[i - 1]) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(segmentTree.max[i - 1] < segmentTree.max[i] ? i - N + 1 : i - N);
                list.add(segmentTree.max[i]);
                result.add(list);
            }
        }
        // 解码
        for (List<Integer> list : result) {
            list.set(0, decodeMap.get(list.get(0)));
        }
        return result;
    }

    public static class SegmentTree {
        private int SIZE;
        private int[] max;
        private int[] change;
        private boolean[] update;

        public SegmentTree(int N) {
            SIZE = N + 1;
            max = new int[SIZE << 2]; // 用来支持脑补概念中，某一个范围的累加和信息
            change = new int[SIZE << 2]; // 用来支持脑补概念中，某一个范围有没有更新操作的任务
            update = new boolean[SIZE << 2]; // 用来支持脑补概念中，某一个范围是否需要更新（而不是更新成0）
        }

        // 之前的所有懒增加、懒更新，从父范围发给左右两个子范围，分发策略是什么
        private void pushDown(int rt) {
            if (update[rt]) {
                update[rt << 1] = true;
                update[rt << 1 | 1] = true;
                change[rt << 1] = change[rt];
                change[rt << 1 | 1] = change[rt];
                max[rt << 1] = Math.max(max[rt << 1], change[rt]);
                max[rt << 1 | 1] = Math.max(max[rt << 1 | 1], change[rt]);
                update[rt] = false;
            }
        }

        // 想要把 L~R 所有的值变成 H
        // 当前影响 l~r，当前范围信息存在数组的 rt 位置
        public void update(int L, int R, int H, int l, int r, int rt) {
            if (L <= l && r <= R) {
                if (H >= max[rt]) {
                    update[rt] = true;
                    change[rt] = H;
                    max[rt] = H;
                }
                return;
            }
            // 当前任务躲不掉，无法懒更新，要往下发一层
            int mid = (l + r) >> 1;
            pushDown(rt);
            if (L <= mid) {
                update(L, R, H, l, mid, rt << 1);
            }
            if (R > mid) {
                update(L, R, H, mid + 1, r, rt << 1 | 1);
            }
        }

        // 把所有的懒更新都下放到底部，类似于自底向上的堆排序
        public void flush() {
            for (int i = max.length - 1; i >= 0; i--) {
                if (max[i] == 0) heapify(i);
            }
        }

        public int heapify(int i) {
            if (i == 0) return 0;
            max[i] = Math.max(max[i], heapify(i / 2));
            return max[i];
        }
    }
}