Easy Understood O(n^2) Solution with explanation
The idea is quite simple, we use intervals to represent the square. the initial height we set to the square cur is pos[1]. That means we assume that all the squ
The idea is quite simple, we use intervals to represent the square. the initial height we set to the square `cur` is `pos[1]`. That means we assume that all the square will fall down to the land. we iterate the previous squares, check is there any square `i` beneath my `cur` square. If we found that we have squares `i` intersect with us, which means my current square will go above to that square `i`. My target is to find the highest square and put square `cur` onto square `i`, and set the height of the square `cur` as \n```java\ncur.height = cur.height + previousMaxHeight;\n``` \nActually, you do not need to use the interval class to be faster, I just use it to make my code cleaner\n\n```java\nclass Solution {\n    private class Interval {\n        int start, end, height;\n        public Interval(int start, int end, int height) {\n            this.start = start;\n            this.end = end;\n            this.height = height;\n        }\n    }\n    public List<Integer> fallingSquares(int[][] positions) {\n        List<Interval> intervals = new ArrayList<>();\n        List<Integer> res = new ArrayList<>();\n        int h = 0;\n        for (int[] pos : positions) {\n            Interval cur = new Interval(pos[0], pos[0] + pos[1] - 1, pos[1]);\n            h = Math.max(h, getHeight(intervals, cur));\n            res.add(h);\n        }\n        return res;\n    }\n    private int getHeight(List<Interval> intervals, Interval cur) {\n        int preMaxHeight = 0;\n        for (Interval i : intervals) {\n            // Interval i does not intersect with cur\n            if (i.end < cur.start) continue;\n            if (i.start > cur.end) continue;\n            // find the max height beneath cur\n            preMaxHeight = Math.max(preMaxHeight, i.height);\n        }\n        cur.height += preMaxHeight;\n        intervals.add(cur);\n        return cur.height;\n    }\n}\n```
['Java']