题目描述

在无限长的数轴（即x轴）上，我们根据给定的顺序放置对应的正方形方块。

第i个掉落的方块(positions[i] = (left, side_length))是正方形，其中left 表示该方块最左边的点位置(positions[i][0])，side_length 表示该方块的边长(positions[i][1])。

每个方块的底部边缘平行于数轴（即x 轴），并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落，并保持静止后，才开始掉落新方块。

方块的底边具有非常大的粘性，并将保持固定在它们所接触的任何长度表面上（无论是数轴还是其他方块）。邻接掉落的边不会过早地粘合在一起，因为只有底边才具有粘性。

返回一个堆叠高度列表ans 。每一个堆叠高度ans[i]表示在通过positions[0], positions[1], ..., positions[i]表示的方块掉落结束后，目前所有已经落稳的方块堆叠的最高高度。

样例1

输入：

[[1, 2], [2, 3], [6, 1]]

输出：

[2, 5, 5]

解释：

第一个方块 positions[0] = [1, 2] 掉落：
_aa
_aa
-------
方块最大高度为 2 。

第二个方块 positions[1] = [2, 3] 掉落：
__aaa
__aaa
__aaa
_aa__
_aa__
--------------
方块最大高度为5。
大的方块保持在较小的方块的顶部，不论它的重心在哪里，因为方块的底部边缘有非常大的粘性。

第三个方块 positions[1] = [6, 1] 掉落：
__aaa
__aaa
__aaa
_aa
_aa___a
-------------- 
方块最大高度为5。

因此，我们返回结果[2, 5, 5]。

算法1

(暴力枚举) $O(n^2)$

• 我们固定一点，然后枚举后面的点会不会落在上面，如果落在上面就更新最大高度
• 最后枚举每个点所对应的最大高度的最大值即为结果

时间复杂度

$O(n^2)$

参考文献

Leetcode

C++ 代码

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size();
        vector<int> q(n);
        vector<int> res(n);
        for(int i = 0; i < positions.size(); i++){
            int l1 = positions[i][0];
            int s1 = positions[i][1];
            int r1 = l1 + s1;
            q[i] += s1;
            for(int j = i + 1; j < positions.size(); j++){
                int l2 = positions[j][0];
                int s2 = positions[j][1];
                int r2 = l2 + s2;
                if(l1 < r2 && l2 < r1){
                    q[j] = max(q[i], q[j]);
                }
            }
        }

        int cur = 0;
        for(int i = 0; i < positions.size(); i++){
            cur = max(cur, q[i]);
            res[i] = cur;
        }
        return res;
    }
};