【从零开始的LeetCode-算法】699. 掉落的方块

在二维平面上的 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 <= 1000
• 1 <= lefti <= 10^8
• 1 <= 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;
    }
}

原文地址：https://blog.csdn.net/qq_40878316/article/details/144315410

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！