Easy Understood TreeMap Solution
The squares divide the number line into many segments with different heights. Therefore we can use a TreeMap to store the number line. The key is the starting p
The squares divide the number line into many segments with different heights. Therefore we can use a TreeMap to store the number line. The key is the starting point of each segment and the value is the height of the segment. For every new falling square (s, l), we update those segments between s and s + l.\n```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        List<Integer> list = new ArrayList<>();\n        TreeMap<Integer, Integer> map = new TreeMap<>();\n\n        // at first, there is only one segment starting from 0 with height 0\n        map.put(0, 0);\n        \n        // The global max height is 0\n        int max = 0;\n\n        for(int[] position : positions) {\n\n            // the new segment \n            int start = position[0], end = start + position[1];\n\n            // find the height among this range\n            Integer key = map.floorKey(start);\n            int h = map.get(key);\n            key = map.higherKey(key);\n            while(key != null && key < end) {\n                h = Math.max(h, map.get(key));\n                key = map.higherKey(key);\n            }\n            h += position[1];\n\n            // update global max height\n            max = Math.max(max, h);\n            list.add(max);\n\n            // update new segment and delete previous segments among the range\n            int tail = map.floorEntry(end).getValue();\n            map.put(start, h);\n            map.put(end, tail);\n            key = map.higherKey(start);\n            while(key != null && key < end) {\n                map.remove(key);\n                key = map.higherKey(key);\n            }\n        }\n        return list;\n    }\n}\n```
[]