408ms Java Solution using linked list


  • 3
    S

    Each time a new building is introduced, we adjust the skyline accordingly. A linked list is used to store the skyline so that node can be easily inserted, appended and removed.

    public class Solution {
        class KeyPoint {
            public int key;
            public int height;
            public KeyPoint next = null;
            
            public KeyPoint(int key, int height) {
                this.key = key;
                this.height = height;
            }
            
        }
        
        public static int[] getKeyPoint(int key, int height) {
            int[] kp = new int[2];
            kp[0] = key;
            kp[1] = height;
            return kp;
        }
        
        public List<int[]> getSkyline(int[][] buildings) {
            KeyPoint head = new KeyPoint(-1,0);
            KeyPoint prevKP = head;
            for (int[] building:buildings) {
                int l = building[0], r = building[1], h= building[2];
                // insert left point
                while (prevKP.next != null && prevKP.next.key <= l) prevKP = prevKP.next;
                int preHeight = prevKP.height;
                if (prevKP.key == l) prevKP.height = Math.max(prevKP.height, h);
                else if (prevKP.height < h) {
                    KeyPoint next = prevKP.next;
                    prevKP.next = new KeyPoint(l, h);
                    prevKP = prevKP.next;
                    prevKP.next = next;
                }
                // insert right point and update points in between
                KeyPoint prev = prevKP, cur = prevKP.next;
                while (cur != null && cur.key < r) {
                    preHeight = cur.height;
                    cur.height = Math.max(cur.height, h);
                    if (cur.height == prev.height)
                        prev.next = cur.next;
                    else
                        prev = cur;
                    cur = cur.next;
                }
                if (prev.height != preHeight && prev.key != r && (cur == null || cur.key != r)) {
                    KeyPoint next = prev.next;
                    prev.next = new KeyPoint(r, preHeight);
                    prev.next.next = next;
                }
            }
            // convert to List<int[]>
            List<int[]> list = new ArrayList<int[]>();
            KeyPoint prev = head, cur = head.next;
            while (cur != null) {
                if (cur.height != prev.height)
                    list.add(getKeyPoint(cur.key, cur.height));
                prev = cur;
                cur = cur.next;
            }
            return list;
        }
    }

  • 0
    G

    Can you please add some explanation here ? It will make it easy to understand


  • 0
    Q

    What's the time complexity? It likes O(N) but it is not, since it needs to find positions to add the new building.


Log in to reply
 

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