题目

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。

返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

实例

思路

目前高度 = 自己高度 + 自己下面踩的高度

自己高度 -> 用一个循环搜索赋值给->sideLength

下面踩的高度 -> 用另外一个循环从零开始找，是不是有在自己下面的方块 存在->他的高度+自己的高度 比较 取max

为什么不是直接赋值，因为存在同一个方块上面有两个方块的情况，这样子就会存在分支，所以不能直接加

这里也用到了动态规划思路，因为每个方块记录的都是自己最高的高度，所以每次取都是取的最大值

最后因为题目每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度

所以再用前面最高高度去更新后面的低高度，因为后面不管怎么放。最高点是不会变的

代码

/*
*fallingSquares:必须记录目前所有已经落稳的 方块堆叠的最高高度
int** positions:二维整数数组,其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi
int positionsSize:行数
int* positionsColSize:列数
int* returnSize:返回值的个数
返回值：一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度
*/

#define MAX(a,b) (a)>(b)?(a):(b)
int* fallingSquares(int** positions, int positionsSize, int* positionsColSize, int* returnSize){
    *returnSize = positionsSize;
    int m = positionsSize;
    int * ans = malloc(sizeof(int) * m);
   // memset(ans , 0 , sizeof(ans));
    int i, j;
    int left1,right1,left2,right2,sideLength;
    for(i = 0; i < m ; i++)
    {
        left1 = positions[i][0];
        sideLength = positions[i][1];
        right1 = positions[i][0] + positions[i][1] - 1;
        ans[i] = sideLength;
        for(j = 0; j < i; j++)
        {
            left2 = positions[j][0];
            right2 = positions[j][0] + positions[j][1] - 1;
            if(left1 <= right2 && right1 >= left2)
            {
                ans[i] = MAX(ans[i],sideLength+ans[j]);
                //ans[i] = sideLength+ans[j];
            }
        }
    } 
    for(i = 1; i < m; i++)
    {
        ans[i] = MAX(ans[i],ans[i-1]);
    }
    return ans;
}