Lazy Segment Tree Solution (22ms)


  • 0
    B
    public class Solution {
        static class TreeNode{
            TreeNode left, right;
            int h;
            boolean isGap;
            TreeNode(int h){
                this.h = h;
                this.left = null;
                this.right = null;
                this.isGap = false;
            }
        }
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<>();
            if(null == buildings) return res;
            int n = buildings.length;
            if(n==0) return res;
            TreeNode root = new TreeNode(-1);
            int  maxEnd = -1;
            for(int [] building : buildings){
                if(maxEnd != -1 && building[0] > maxEnd){
                    update(root, 0, Integer.MAX_VALUE, maxEnd, maxEnd, 0);// isGap
                }
                update(root, 0, Integer.MAX_VALUE, building[0], building[1], building[2]);
                // System.out.println("-----------");
                maxEnd = Math.max(maxEnd, building[1]);
            }
            
            query(root, 0, Integer.MAX_VALUE, res);
            res.add(new int[] {maxEnd, 0});
            // Collections.sort(res, new Comparator<int[]>(){
            //     @Override
            //     public int compare(int [] arr1, int [] arr2){
            //         return arr1[0]-arr2[0];
            //     }
            // });
            return res;
        }
        void update(TreeNode root, int l, int r, int ql, int qr, int h){
            if(l == ql && r == qr && root.left == null && root.right == null){// lazy
                root.h = Math.max(root.h, h);
                if(h == 0) root.isGap = true;
                // System.out.println(l + "\t" +r + "\t" + root.h);
                return;
            }
            
            int mid = l + (r-l) /2;
            
            if(root.h >= 0){
                if(root.left == null) root.left = new TreeNode(-1);
                update(root.left, l, mid, l, mid, root.h);
                if(root.right == null) root.right = new TreeNode(-1);
                update(root.right, mid+1, r, mid+1, r, root.h);
                root.h = -1;
            }
            
            if(mid >= qr) {
                if(root.left == null) root.left = new TreeNode(-1);
                update(root.left, l, mid, ql, qr, h);
            }
            else if(mid < ql){
                if(root.right == null) root.right = new TreeNode(-1);
                update(root.right, mid+1, r, ql, qr, h);
            } 
            else{
                if(root.left == null) root.left = new TreeNode(-1);
                if(root.right == null) root.right = new TreeNode(-1);
                update(root.left, l, mid, ql, mid, h);
                update(root.right, mid+1, r, mid+1, qr, h);
            }
        }
        
        void query(TreeNode root, int l, int r, List<int[]> res){
            if(root == null) return;
            if(root.h >= 0){
                // System.out.println(l + "\t" + r + "\t" + root.h);
                if(res.isEmpty() || res.get(res.size()-1)[1] != root.h){
                    if(!res.isEmpty() && res.get(res.size()-1)[1] > root.h) res.add(new int[] {l-1, root.h});
                    else res.add(new int[] {l, root.h});
                }
                if(root.isGap){
                    res.add(new int[] {l, 0});
                }
                return;
            }
            int mid = l + (r-l)/2;
            query(root.left, l, mid, res);
            query(root.right, mid+1, r, res);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.