c++, map based short solution
The running time complexity should be O(n\xb2), since the bottleneck is given by finding the maxHeight in certain range.\nIdea is simple, we use a map, and map[
The running time complexity should be O(n\xb2), since the bottleneck is given by finding the maxHeight in certain range.\nIdea is simple, we use a map, and ```map[i] = h``` means, from ```i``` to next adjacent x-coordinate, inside this range, the height is ```h```.\nTo handle edge cases like adjacent squares, I applied STL functions, for left bound, we call ```upper_bound``` while for right bound, we call ```lower_bound```.\nSpecial thanks to @storypku for pointing out bad test cases like [[1,2],[2,3],[6,1],[3,3],[6,20]]\n\n```\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        map<int,int> mp = {{0,0}, {INT_MAX,0}};\n        vector<int> res;\n        int cur = 0;\n        for(auto &p : positions){\n            int l = p.first, r = p.first + p.second, h = p.second, maxH = 0;\n            auto ptri = mp.upper_bound(l), ptrj = mp.lower_bound(r);        // find range\n            int tmp = ptrj->first == r? ptrj->second : (--ptrj)++->second;  // tmp will be applied by new right bound \n            for(auto i = --ptri; i != ptrj; ++i)\n                maxH = max(maxH, i->second);                                // find biggest height\n            mp.erase(++ptri, ptrj);                                         // erase range\n            mp[l] = h+maxH;                                                 // new left bound\n            mp[r] = tmp;                                                    // new right bound\n            cur = max(cur, mp[l]);\n            res.push_back(cur);\n        }\n        return res;\n    }\n```
[]