3ms fastest java solution beat 99.95%


  • 1
    U

    Each node represents a "key point",use node to devide the scope,
    When add a new node, devide a scope into two small scopes.
    So every triple can be represented as two nodes.
    Then set every influenced scopes to higher height, finally merge the same height scopes;

    If you want time in 3ms, you can use new int[2] to replace node.l,and node.h; To let code concise, I use later (4ms).
    ....May I ask for your vote? Thanks!

    import java.util.*;
    //use two-way linked list with first and last node
    class Node{
        int l, h;                          //int[] a = new int[2] 
        Node pri, next;
    
        Node (int x, int y)    {    l = x;    h = y;   }
    
        public void add (Node n)    {  //add Node n before!!!!this node    
            n.next = this;
            n.pri = pri;
            pri.next = n;
            pri = n;
        }
    
        public static void del (Node n)    {  //delete Node n
            n.pri.next = n.next;
            n.next.pri = n.pri;
        }
    }
    
    public class Solution    {
        public List<int[]> getSkyline (int[][] b)    {
            List<int[]> list = new ArrayList<int[]> ();
            int n = b.length;
            if (n == 0)
                return list;
            //unity add delete operation
            Node first = new Node (0, 0);
            Node last = new Node (0, 0);
            first.next = last;
            last.pri = first;        
            
            last.add (new Node (b[0][0], b[0][2]));
            last.add (new Node (b[0][1], 0));
    
            Node p = first.next;
    
            for (int i = 1; i < n; i++)   {
                int l = b[i][0];
                int r = b[i][1];
                int h = b[i][2];
                
                if (h <= p.h && r <= p.next.l)  //no need change
                    continue;
    
                Node start = p;
    
                int lastH = p.h;
                Node nextStart = p;
                if (l == p.l)  //no need add new Node
                    p.h = Math.max (h, p.h);
                else    {  //insert the start node    
                    while (p != last && p.l < l)                
                        p = p.next;
    
                    lastH = p.pri.h;
                    nextStart = p.pri;
                    p.add (new Node (l, Math.max (h, lastH)));
                }
    
                while (p != last && p.l < r)     {   //set height of node between l and r
                    lastH = p.h;
                    p.h = Math.max (h, p.h);
                    p = p.next;
                }
    
                if (p.l != r)   //insert end node, the height of end node is lastH
                    p.add (new Node (r, lastH));
    
                Node end = p;
    
                p = start;            
                while (p.next != end)    {   //merge Nodes of equal height
                    if (p.h == p.next.h)
                        Node.del (p.next);
                    else
                        p = p.next;
                }
    
                p = nextStart;
            }
    
            p = first.next;
            while (p != last)    {
                list.add (new int[] {p.l, p.h});
                p = p.next;
            }   
            
            return list;
        }
    }
    
    

Log in to reply
 

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