24 ms solution using segment tree


  • 0
    A
    public class Solution {
        class TreeNode {
            int left;
            int right;
            int height;
            TreeNode leftChild = null;
            TreeNode rightChild = null;
            public TreeNode(int l, int r, int h) {
                left = l;
                right = r;
                height = h;
            }
        }
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> result = new ArrayList<>();
            if (buildings == null || buildings.length == 0 || buildings[0].length == 0) return result;
            int[] leftAndRightEnd = findLeftAndRightEnd(buildings);
            int leftEnd = leftAndRightEnd[0];
            int rightEnd = leftAndRightEnd[1];
            TreeNode root = new TreeNode(leftEnd, rightEnd, 0);
            for (int[] building : buildings) {
                insertInTree(root, building[0], building[1] - 1, building[2]);
            }
            traverseAndFindKeyPoints(root, result);
            return collapse(result);
        }
        
        List<int[]> collapse(List<int[]> keyPoints) {
            List<int[]> result = new ArrayList<>();
            result.add(keyPoints.get(0));
            int[] lastKeyPoint = keyPoints.get(0);
            for (int i = 1; i < keyPoints.size(); i++) {
                int[] keyPoint = keyPoints.get(i);
                if (keyPoint[1] != lastKeyPoint[1]) {
                    result.add(keyPoint);
                    lastKeyPoint = keyPoint;
                }
            }
            return result;
        }
        
        int[] findLeftAndRightEnd(int[][] buildings) {
            int[] result = new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE};
            for (int[] building : buildings) {
                result[0] = Math.min(result[0], building[0]);
                result[1] = Math.max(result[1], building[1]);
            }
            return result;
        }
        
        void insertInTree(TreeNode root, int left, int right, int height) {
            if (root == null) return;
            if (left > root.right || right < root.left) return;
            int mid = root.left / 2 + root.right / 2;
            if (root.left >= left && root.right <= right) {
                root.height = Math.max(root.height, height);
                if (root.leftChild == null && root.rightChild == null) return;
            }
            
            makeChildrenIfApplicable(root, mid);
            
            if (left < mid + 1) {
                insertInTree(root.leftChild, left, right, height);
            }
            if (right > mid) {
                insertInTree(root.rightChild, left, right, height);
            }
        }
        
        void makeChildrenIfApplicable(TreeNode root, int mid) {
            if (mid == root.right) return;
            if (root.leftChild == null) root.leftChild = new TreeNode(root.left, mid, root.height);
            if (root.rightChild == null) root.rightChild = new TreeNode(mid + 1, root.right, root.height);
        }
        
        void traverseAndFindKeyPoints(TreeNode root, List<int[]> result) {
            if (root == null) return;
            
            traverseAndFindKeyPoints(root.leftChild, result);
            if (root.leftChild == null && root.rightChild == null) {
                result.add(new int[]{root.left, root.height});
            }
            traverseAndFindKeyPoints(root.rightChild, result);
        }
    }
    

Log in to reply
 

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