Java实现 LeetCode 699 掉落的方块（线段树？）

谁借莪１个温暖的怀抱￠ 2023-07-23 05:57 3阅读 0赞

## 699. 掉落的方块 ##

在无限长的数轴（即 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]。

示例 2:

输入: [[100, 100], [200, 100]]
    输出: [100, 100]
    解释: 相邻的方块不会过早地卡住，只有它们的底部边缘才能粘在表面上。

注意:

1 <= positions.length <= 1000.  
1 <= positions\[i\]\[0\] <= 10^8.  
1 <= positions\[i\]\[1\] <= 10^6.

PS：  
按照左端点放进树

import java.util.*;
    
    class Solution { 
        // 描述方块以及高度
        private class Node { 
            int l, r, h, maxR;
            Node left, right;
    
            public Node(int l, int r, int h, int maxR) { 
                this.l = l;
                this.r = r;
                this.h = h;
                this.maxR = maxR;
                this.left = null;
                this.right = null;
            }
        }
    
        //
        public List<Integer> fallingSquares(int[][] positions) { 
            // 创建返回值
            List<Integer> res = new ArrayList<>();
            // 根节点，默认为零
            Node root = null;
            // 目前最高的高度
            int maxH = 0;
    
            for (int[] position : positions) { 
                int l = position[0]; // 左横坐标
                int r = position[0] + position[1]; // 右横坐标
                int e = position[1]; // 边长
                int curH = query(root, l, r); // 目前区间的最高的高度
                root = insert(root, l, r, curH + e);
                maxH = Math.max(maxH, curH + e);
                res.add(maxH);
            }
            return res;
        }
    
        private Node insert(Node root, int l, int r, int h) { 
            if (root == null) return new Node(l, r, h, r);
            if (l <= root.l)
                root.left = insert(root.left, l, r, h);
            else
                root.right = insert(root.right, l, r, h);
            // 最终目标是仅仅需要根节点更新 maxR
            root.maxR = Math.max(r, root.maxR);
            return root; // 返回根节点
        }
    
        private int query(Node root, int l, int r) { 
            // 新节点的左边界大于等于目前的maxR的话，直接得到0，不需要遍历了
            if (root == null || l >= root.maxR) return 0; 
            // 高度
            int curH = 0;
            if (!(r <= root.l || root.r <= l)) // 是否跟这个节点相交
                curH = root.h;
            // 剪枝
            curH = Math.max(curH, query(root.left, l, r));
            if (r > root.l)
                curH = Math.max(curH, query(root.right, l, r));
            return curH;
        }
    }