Java ordered linked list, beat 100%, 11ms


  • 1
    I
        class Node {
            int x, h;
            Node next;
            Node(int x, int h) {
                this.x = x;
                this.h = h;
            }
        }
        public List<Integer> fallingSquares(int[][] positions) {
            int n = positions.length, max = 0;
            List<Integer> ans = new ArrayList<>();
            Node head = new Node(0, 0);
            for (int[] p : positions) {
                Node prev = head;
                while (prev.next != null && prev.next.x < p[0]) {
                    prev = prev.next;
                }
                int lasth = prev.h;
                int h = (prev.next == null || prev.next.x > p[0]) ? prev.h + p[1] : p[1];
                Node post = prev.next;
                while (post != null && post.x < p[0] + p[1]) {
                    h = Math.max(h, post.h + p[1]);
                    lasth = post.h;
                    post = post.next;
                }
                Node cur = new Node(p[0], h);
                prev.next = cur;
                if (post == null || post.x > p[0] + p[1]) {
                    cur.next = new Node(p[0] + p[1], lasth);
                    cur = cur.next;
                }
                cur.next = post;
                max = Math.max(max, h);
                ans.add(max);
            }
            return ans;
        }
    

Log in to reply
 

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