力扣218.天际线问题 线段树解法

原题

官解用的扫描线 + 优先队列方法，但是一开始没想的那么麻烦，只觉得这么有多区间，直觉暴力线段树，也提供一种思路

class Solution {
    //用线段树的结点范围代表x轴 结点值代表这段x轴内的最高高度
    //建完树之后如何获得答案呢？ 再次遍历buildings数组
    //遍历每个建筑的左上点和右下点 如果其是这个区间最高点 就加入答案
    public List<List<Integer>> getSkyline(int[][] buildings) { //buildings[i] = [lefti, righti, heighti]
        int n = buildings.length;
        N = 1;
        for (int i = 0; i < n; i++) {
            N = Math.max(N, buildings[i][1]);// 找出线段树的范围 可以省一点时间
        }

        // 注意！区间最值的更新，为了避免覆盖情况，比如[15,20,10]和[19,24,8]，需要按区间高度先排序
        Arrays.sort(buildings, (o1,o2) -> o1[2]-o2[2]);//按高度从小到大排序 这样就不会产生错误覆盖

        List<Integer> points = new ArrayList<>(); //存储边界坐标点

        for (int[] building : buildings) {
            int l = building[0],r=building[1],h=building[2];
            points.add(l);
            points.add(r);
            update(root,0,N,l,r-1,h);//建树 注意！ 右边界的高度不算 防止端点覆盖
        }
        Collections.sort(points);//对坐标点排序
        points = points.stream().distinct().collect(Collectors.toList());//去除重复坐标点
        List<List<Integer>> ans = new ArrayList<>();//答案数组

        for (int i = 1; i < points.size(); i++) {
            int heigh=(int)query(root,0,N,points.get(i-1),points.get(i)-1);
            int j=i+1;
            while (j<points.size() && query(root,0,N,points.get(j-1),points.get(j)-1)==heigh) j++;//相同高度不算在天际线里
            ans.add(Arrays.asList(points.get(i-1),heigh));
            i = j-1;
        }
        ans.add(Arrays.asList(points.get(points.size()-1),0));//最后一个点坐标单独判断
        return ans;
    }

    //下面为线段树模版
    class Node {
        Node left, right;
        long val, add;
    }

    private int N;//线段树范围大小
    private Node root = new Node();


    public void update(Node node, long start, long end, long l, long r, long val) {
        if (l <= start && end <= r) {
            node.val = val;
            node.add = val;
            return;
        }
        long mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }

    // 在区间 [start, end] 中查询区间 [l, r] 的结果
    public long query(Node node, long start, long end, long l, long r) {
        if (l <= start && end <= r) return node.val;
        long mid = (start + end) >> 1, ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans = query(node.left, start, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
        return ans;
    }

    // 向上更新
    private void pushUp(Node node) {
        node.val = Math.max(node.left.val, node.right.val);
    }

    // 推懒惰标记的函数
    private void pushDown(Node node, long leftNum, long rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return;
        node.left.val = node.add;
        node.right.val = node.add;
        node.left.add = node.add;
        node.right.add = node.add;
        node.add = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87