LeetCode 699 掉落的方块

方法1：暴力

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        n = len(positions); ans = [0] * n  # 记录每个方块落下后的高度
        for i, (left0, widen0) in enumerate(positions):
            height = widen0  # 默认
            right0 = left0 + widen0  # 右边界
            for j in range(i):  # 遍历前 i - 1 个判定叠加高度
                left, widen = positions[j]
                right = left + widen
                if  right0 > left and left0 < right:  # 当前方块会落在第 j 块的上方
                    height = max(height, ans[j] + widen0)
            ans[i] = height
        for i in range(1, n):
            ans[i] = max(ans[i - 1], ans[i])
        return ans

• ArrayList 添加add() / 获取get() / 修改set()

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        List<Integer> heights = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) { // 对于每一个方块
            int left0 = positions[i][0];
            int right0 = positions[i][0] + positions[i][1];
            int height = positions[i][1];  // 默认高度
            for (int j = 0; j < i; j++) { // 遍历 i - 1 个方块
                int left = positions[j][0];
                int right = positions[j][0] + positions[j][1];
                if (right0 > left && left0 < right) 
                    height = Math.max(height, heights.get(j) + positions[i][1]);
            }
            heights.add(height);
        }
        for (int i = 1; i < n; i++) {
            heights.set(i, Math.max(heights.get(i - 1), heights.get(i)));
        }
        return heights;
    }
}

方法2：线段树

• defaultdict 默认字典

class DynamicSegmentTree:
    """动态开点线段树模板 关键在于使用 defaultdict 来存储左右儿子"""

    def __init__(self):
        self.val = defaultdict(int)
        self.add = defaultdict(int)

    # 将区间 [L, R] 内的数据都更新为 v; o 的左右儿子 lson / rson
    def update(self, o: int, lson: int, rson: int, L: int, R: int, v: int) -> None:
        if L <= lson and rson <= R:  # 整个[lson, rson]需要修改
            self.do(o, v)
            return
        self.pushdown(o)  # 区间未覆盖 懒标记需要向下传递
        mid = (lson + rson) >> 1
        if mid >= L:  # [L, R] 区间包含了一部分左儿子
            self.update(o << 1, lson, mid, L, R, v)
        if mid < R:  # [L, R] 区间包含了一部分右儿子
            self.update(o << 1 | 1, mid + 1, rson, L, R, v)
        self.pushup(o)  # 将修改后的结果向上传递

    def pushup(self, o: int) -> None:
        self.val[o] = max(self.val[o << 1], self.val[o << 1 | 1])

    def pushdown(self, o: int) -> None:
        v = self.add[o]
        if v == 0:
            return
        self.do(o << 1, v)  # 给左儿子
        self.do(o << 1 | 1, v)  # 给右儿子
        self.add[o] = 0

    def do(self, o: int, v: int) -> None:
        self.val[o] = max(self.val[o], v)  # 本题存储的高度
        self.add[o] = max(self.add[o], v)

    # 查询区间 [L, R] 内的高度最大值
    def query(self, o: int, lson: int, rson: int, L: int, R: int) -> int:
        if L <= lson and rson <= R:
            return self.val[o]
        self.pushdown(o)  # 将懒标签向下传递
        res = 0; mid = (lson + rson) >> 1
        if mid >= L:
            res = self.query(o << 1, lson, mid, L, R)
        if mid < R:
            res = max(res, self.query(o << 1 | 1, mid + 1, rson, L, R))
        return res

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ans = list(); N = 10 ** 9 + 1; Max = 0  # 记录当前最高值
        st = DynamicSegmentTree()
        for left, widen in positions:
            # 查询 [left, left + widen - 1] 区间内高度的最大值
            curH = st.query(1, 1, N, left, left + widen - 1)
            Max = max(Max, curH + widen); ans.append(Max)
            # 更新 [left, left + widen - 1] 区间内的高度为 curH + widen
            st.update(1, 1, N, left, left + widen - 1, curH + widen)
        return ans

class Solution {
    class Node {
        int val, add;  // 存储的值和懒标记
        int lson, rson;  // 左右儿子所在下标
    }

    int N = 1000_000_000 + 1;  // 管辖区间的最大值
    int cnt = 0;  // 节点个数并在生成节点时完成节点之间的连接
    Node[] tree = new Node[1000010];

    // 更新 [L, R] 区间的值为 v; lson / rson 为 o 管辖的区间范围
    void update(int o, int lson, int rson, int L, int R, int v) {
        if (L <= lson && rson <= R) {
            work(o, v);
            return ;
        }
        pushdown(o);  // 将懒标记向下传递
        int mid = (lson + rson) >> 1;
        if (mid >= L)
            update(tree[o].lson, lson, mid, L, R, v);
        if (mid < R)
            update(tree[o].rson, mid + 1, rson, L, R, v);
        pushup(o);
    } 
    
    void pushup(int o) {
        tree[o].val = Math.max(tree[tree[o].lson].val, tree[tree[o].rson].val);
    }

    void work(int o, int v) {
        tree[o].val = Math.max(tree[o].val, v);
        tree[o].add = Math.max(tree[o].add, v);
    }

    void pushdown(int o) {
        // 当前节点未创建
        if (tree[o] == null) tree[o] = new Node();
        if (tree[o].lson == 0) {  // 左边空新建左节点
            tree[o].lson = ++cnt;
            tree[tree[o].lson] = new Node();
        }
        if (tree[o].rson == 0) {  // 右边空新建右节点
            tree[o].rson = ++cnt;
            tree[tree[o].rson] = new Node();
        }
        int v = tree[o].add;
        if (v == 0) return ;
        work(tree[o].lson, v);
        work(tree[o].rson, v);
        tree[o].add = 0;
    }

    // 查询 [L, R] 区间内高度最大值
    int query(int o, int lson, int rson, int L, int R) {
        if (L <= lson && rson <= R) 
            return tree[o].val;
        pushdown(o);
        int mid = (lson + rson) >> 1, res = 0;
        if (mid >= L)
            res = query(tree[o].lson, lson, mid, L, R);
        if (mid < R)
            res = Math.max(res, query(tree[o].rson, mid + 1, rson, L, R));
        return res;
    }

    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        tree[1] = new Node();  // tree[1].val 保存着实时最大值
        for (int[] info : positions) {
            int left = info[0], widen = info[1];
            int cur = query(1, 1, N, left, left + widen - 1);
            update(1, 1, N, left, left + widen - 1, cur + widen);
            ans.add(tree[1].val);
        }
        return ans;
    }
}