It is Miraculours!! Beat 99.9% java SelfDefined SegmentListNode solution ,3ms,with explanation O(n) space complexity and o(n)time


  • 2
    T

    first we analyse this problem : every building likes a segment ; when the high building come it will insert in the structure and change the segment it covered like the picture below:
    just[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] :
    first [2,9,10] :
    0_1482142537810_1.PNG
    2)[3,7,15]
    0_1482142801966_upload-1f30a2fe-4fb4-4249-a4dc-f4218ff01d63
    3)[5,12,12]
    0_1482142987915_upload-95a866bc-4bd4-4c2e-8335-d34936ab4767
    ...
    it is just like the function f(x) = [x];
    so i design a stucture which will record the left of segment right of segment and the height meanwhile record the next segment just like linkedList
    when a building come in find the left in the Segment list whose the interval contains the left; then find the right ; and insert this segment in ,meanwhile you should change the node between the interval of the segment in following rules recursivly:

    1. it is lower than the height, it will be blocked,make the height = height'
    2. it is higher than the height it will block the segment so continue;
      final detete the dumplicate node with the same height;

    and we should pay attention to the situation when left = left'; right = right'; curNode.next = null we will deal with specially; it is noted in the program
    in this function we just swipe the buildings arr once we will get the skyline

    the code :

     /**
         * Gaussian function y = [x]
         */
    
        class SegNode {
            int begin;
            int end;
            int high;
            SegNode next = null;
    
            SegNode(int begin, int end, int high) {
                this.begin = begin;
                this.end = end;
                this.high = high;
            }
        }
    
        class SegTree {
            SegNode root;
            SegNode cur = null;
    
            SegTree() {
                root = new SegNode(0, 0, 0);
            }
            /**
             * insert a node in the segTree
             * @param arr :arr[0] : the begin of the interval
             *             arr[1]: the end of the interval
             *             arr[2] : the weight of the interval
             * */
            void insertSegNode(int[] arr) {
                if (cur == null) {
                    root.next = new SegNode(arr[0], arr[1], arr[2]);
                    cur = root.next;
                } else {
                    SegNode str = InsertStart(cur, arr);
                    if (str == null) return;
                    cur = str;
                    InsertEnd(str, arr);
                    /*deleteDuplicate(str);*/
                }
            }
            /**
             * find the end interval that the end of the node insert in
             * */
            private SegNode InsertEnd(SegNode node, int[] arr) {
                //right is in [begin,end)
                if (arr[1] >= node.begin && arr[1] < node.end) {
                    if (node.high < arr[2]) {
                        SegNode tmp = node.next;
                        SegNode node1 = new SegNode(arr[1], node.end, node.high);
                        node1.next = tmp;
                        node.end = arr[1];
                        node.high = arr[2];
                        node.next = node1;
                    }
                    return node;
                } else {
                    // the insert segment's height lower than node continue; higher make the node.high = height
                    node.high = node.high < arr[2] ? arr[2] : node.high;
                    if (node.end == arr[1]) return null;
                    if (node.next == null) {
                        if (node.high <= arr[2]) {
                            node.end = arr[1];
                        } else {
                            node.next = new SegNode(node.end, arr[1], arr[2]);
                        }
                        return null;
                    }
                    SegNode node1 = InsertEnd(node.next, arr);
                    //backtracking delete the dumplicate node :[1,2,5],[2,5,5] ->[1,5,5]
                    if (node1 != null && node1.high == node.high) {
                        node.end = node1.end;
                        node.next = node1.next;
                    }
                    return node1;
                }
            }
            /**
             * find the the interval that the begin of the node insert in
             * */
            private SegNode InsertStart(SegNode node, int[] arr) {
                //when the left val int [begin,end)
                if (arr[0] >= node.begin && arr[0] < node.end) {
                    if (arr[0] > node.begin) {
                        if (arr[2] > node.high) {
                            SegNode node1 = new SegNode(arr[0], node.end, node.high);
                            node.end = arr[0];
                            node1.next = node.next;
                            node.next = node1;
                            node = node.next;
    
                        }
                    }
                    return node;
                } else {
                    //when the node.next == null
                    if (node.next == null) {
                        //left == end
                        if (node.end == arr[0]) {
                            if (arr[2] == node.high) {
                                node.end = arr[1];
                            } else {
                                node.next = new SegNode(arr[0], arr[1], arr[2]);
                                cur = node.next;
                            }
                        } else {
                            SegNode node0 = new SegNode(node.end, arr[0], 0);
                            SegNode node1 = new SegNode(arr[0], arr[1], arr[2]);
                            node.next = node0;
                            node0.next = node1;
                            cur = node1;
                        }
    
                        return null;
                    }
                    return InsertStart(node.next, arr);
                }
            }
    
        }
    
        public List<int[]> getSkyline(int[][] buildings) {
            if (buildings.length == 0) return new ArrayList<>();
            List<int[]> res = new ArrayList<>();
            SegTree dic = new SegTree();
            for (int[] build : buildings) {
                dic.insertSegNode(build);
            }
            SegNode node = dic.root.next;
            SegNode pre = dic.root;
            while (node != null) {
                if (node.high != pre.high) {
                    int[] a = new int[2];
                    a[0] = node.begin;
                    a[1] = node.high;
                    res.add(a);
                }
                node = node.next;
                pre = pre.next;
            }
            int[] a = new int[2];
            a[0] = pre.end;
            a[1] = 0;
            res.add(a);
            return res;
        }
    

    any question or improvement


  • 0
    D

    It's smart of you to keep a next pointer in the tree node for easier iteration.

    My solution without next runs in 38ms.

    public class Solution {
        // segment tree
        class TreeNode {
            int start;
            int end;
            int height;
            TreeNode left;
            TreeNode right;
            
            TreeNode(int _start, int _end, int _height) {
                start=_start;
                end=_end;
                height=_height;
            }
            
            void add(TreeNode n) {
                if (n.end <= start) {
                    if (left==null) {
                        left = n;
                    } else {
                        left.add(n);
                    }
                } else if (end <=n.start) {
                    if (right==null) {
                        right = n;
                    } else {
                        right.add(n);
                    }
                } else {
                    TreeNode l=null, r=null;
                    if (n.start>=start && n.end <=end && height >= n.height) return;
                    if (n.start > start) {
                        l = new TreeNode(start, n.start, height);
                    } else if (n.start < start) {
                        l = new TreeNode(n.start, start, n.height);
                    }
                    
                    if (n.end < end) {
                        r = new TreeNode(n.end, end, height);
                    } else if (n.end > end) {
                        r = new TreeNode(end, n.end, n.height);
                    }
                    start = Math.max(start, n.start);
                    end = Math.min(end, n.end);
                    height = Math.max(height, n.height);
                    if (l!=null) add(l);
                    if (r!=null) add(r);
                }
            }
        }
        public List<int[]> getSkyline(int[][] buildings) {
            LinkedList<int[]> ret = new LinkedList<>();
            if (buildings.length==0) return ret;
            TreeNode root=new TreeNode(0,Integer.MAX_VALUE,0);
            
            for (int[] coord: buildings) {
                root.add(new TreeNode(coord[0], coord[1], coord[2]));
            }
            
            Deque<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            Map<TreeNode, Boolean> expanded = new HashMap<>();
            
            // inorder 
            while (!stack.isEmpty()) {
                TreeNode n = stack.pop();
                if (n==null) continue;
                if (expanded.getOrDefault(n, false) || n.left==null && n.right==null) {
                    // revisit
                    // skip same height
                    if (ret.size()==0 || ret.get(ret.size()-1)[1] != n.height)
                        ret.add(new int[]{n.start, n.height});
                    continue;
                }
                
                stack.push(n.right);
                stack.push(n);
                stack.push(n.left);
                
                expanded.put(n, true);
            }
            
            if (buildings[0][0]!=0) ret.pop();
            if (ret.get(ret.size()-1)[1]==Integer.MAX_VALUE) ret.add(new int[]{Integer.MAX_VALUE, 0});
            
            return ret;
        }
    }
    

  • 0
    T

    @derek3 I think your function is more easy to understand ~,mine is difficult to read


Log in to reply
 

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