• 力扣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
  • 相关阅读:
    Leetcode171. Excel 表列序号
    剑指 Offer II 068. 查找插入位置
    java毕业设计大学生心愿墙系统Mybatis+系统+数据库+调试部署
    【BOOST C++ 13 并行编程】(1) Boost.Thread
    声卡喊话IP喇叭,IP网络吸顶天花喇叭
    【文件输入输出流】Inputstream和Outputstream
    Hack_Kid
    写了个 Markdown 命令行小工具,希望能提高园友们发文的效率!
    sklearn【F1 Scoree】F1分数原理及实战代码!
    单核与多核CPU的区别与联系-结合ESP32浅谈
  • 原文地址:https://blog.csdn.net/weixin_43739821/article/details/134242459