在二维平面上的 x 轴上，放置着一些方块。
给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。
在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。
示例 1：
输入：positions = [[1,2],[2,3],[6,1]] 输出：[2,5,5] 解释： 第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。 第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。 第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。 因此，返回 [2, 5, 5] 作为答案。
示例 2：
输入：positions = [[100,100],[200,100]] 输出：[100,100] 解释： 第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。 第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。 因此，返回 [100, 100] 作为答案。 注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。
提示：
1 <= positions.length <= 10001 <= lefti <= 10^81 <= sideLengthi <= 10^6
我的解答：
class Solution {public List<Integer> fallingSquares(int[][] positions) {// 记录各部分的高List<int[]> heigh = new ArrayList<int[]>();List<Integer> res = new ArrayList<Integer>();int max = 0;for(int[] p : positions){// 当前掉落方块的左右侧x坐标，及其高度int px_1 = p[0],px_2 = p[1] + p[0], ph = p[1];int cur_h = ph;// 遍历已固定的方块for(int i = 0;i < heigh.size();i++){// 固定方块的左右侧x坐标，及其高度int hx_1 = heigh.get(i)[0], hx_2 = heigh.get(i)[1], hh = heigh.get(i)[2];// 掉落方块未落在当前固定方块上方if(px_1 >= hx_2 || px_2 <= hx_1) continue;// 掉落方块落在当前固定方块上方，且左侧在其左侧右方if(px_1 >= hx_1){// 右侧对齐，则移除该固方块if(px_1 == hx_1) heigh.remove(i--);// 未对齐，则缩小固定方块落地长度else heigh.get(i)[1] = px_1;// 如果掉落方块右侧小于固定方块右侧，那么就新增方块记录为可作为落点的新固定方块if(px_2 < hx_2) heigh.add(new int[]{px_2, hx_2, hh});}//掉落方块落在当前固定方块上方，且左侧在其左侧左方else{ // 如果掉落方块的右侧在固定方块右侧的右方，那么说明掉落方块将固定方块覆盖掉了if(px_2 >= hx_2) heigh.remove(i--);// 若没有全覆盖，那么就缩短固定方块的左侧落点位置else heigh.get(i)[0] = px_2;}// 掉落方块能落在该固定方块上，那么长度等于固定方块的高度+自身高度cur_h = Math.max(cur_h, ph + hh);}heigh.add(new int[]{px_1, px_2, cur_h}); // 将当前方块加入heigh数组中max = Math.max(max, cur_h); // 比较是否为当前最高高度res.add(max);}return res;}
}
