likes
comments
collection
share

699. 掉落的方块 : 线段树（动态开点）的两种方式

作者站长头像
站长
· 阅读数 43

题目描述

这是 LeetCode 上的 699. 掉落的方块 ，难度为 困难。

Tag : 「线段树（动态开点）」、「线段树」

在无限长的数轴（即 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<=10001 <= positions.length <= 10001<=positions.length<=1000
  • 1<=positions[i][0]<=1081 <= positions[i][0] <= 10^81<=positions[i][0]<=108
  • 1<=positions[i][1]<=1061 <= positions[i][1] <= 10^61<=positions[i][1]<=106

基本分析

为了方便，我们使用 ps 来代指 positions。

每次从插入操作都附带一次询问，因此询问次数为 1e31e31e3，左端点的最大值为 10e810e810e8，边长最大值为 1e61e61e6，由此可知值域范围大于 1e81e81e8，但不超过 1e91e91e9。

对于值域范围大，但查询次数有限的区间和问题，不久前曾经总结过 : 求解常见「值域爆炸，查询有限」区间问题的几种方式，可作为前置 🧀 进行了解。

而我的个人习惯，一般要么使用「离散化 + 线段树」，要么使用「线段树（动态开点）」进行求解。

本题为「非强制在线」问题，因此可以先对 ps 数组进行离散化，将值域映射到较小的空间，然后套用固定占用 4×n4 \times n4×n 空间的线段树求解。

但更为灵活（能够同时应对强制在线问题）的求解方式是「线段树（动态开点）」。

同时实现动态开点的方式有两种：

  1. 根据操作次数对使用到的最大点数进行预估，并采用数组方式进行实现线段树（解法一）；
  2. 使用动态指针（解法二）；

方式一在不久之前的每日一题 933. 最近的请求次数 讲过，因此今天把方式二也写一下。

具体的，我们将顺序放置方块的操作（假设当前方块的左端点为 aaa，边长为 lenlenlen，则有右端点为 b=a+lenb = a + lenb=a+len），分成如下两步进行：

  • 查询当前范围 [a,b][a, b][a,b] 的最大高度为多少，假设为 curcurcur；
  • 更新当前范围 [a,b][a, b][a,b] 的最新高度为 cur+lencur + lencur+len。

因此这本质上是一个「区间修改 + 区间查询」的问题，我们需要实现带「懒标记」的线段树，从而确保在进行「区间修改」时复杂度仍为 O(log⁡n)O(\log{n})O(logn)。

另外有一个需要注意的细节是：不同方块之间的边缘可以重合，但不会导致方块叠加，因此我们当我们对一个区间 [a,b][a, b][a,b] 进行操作（查询或插入）时，可以将其调整为 [a,b−1][a, b - 1][a,b−1]，从而解决边缘叠加操作高度错误的问题。

线段树（动态开点 - 估点）

估点的基本方式在前置 🧀 求解常见「值域爆炸，查询有限」区间问题的几种方式 详细讲过。

简单来说，可以直接估算为 6×m×log⁡n6 \times m \times \log{n}6×m×logn 即可，其中 mmm 为询问次数（对应本题就是 ps 的长度），而 nnn 为值域大小（对应本题可直接取成 1e91e91e9）；而另外一个比较实用（避免估算）的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（不考虑字节对齐，或者结构体过大的情况，Java 的 128M128M128M 可以开到 5×1065 \times 10^65×106 以上）。

代码：

class Solution {
    class Node {
        // ls 和 rs 分别代表当前区间的左右子节点所在 tr 数组中的下标
        // val 代表当前区间的最大高度，add 为懒标记
        int ls, rs, val, add;
    }
    int N = (int)1e9, cnt = 0;
    Node[] tr = new Node[1000010];
    void update(int u, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            tr[u].val = v;
            tr[u].add = v;
            return ;
        }
        pushdown(u);
        int mid = lc + rc >> 1;
        if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return tr[u].val;
        pushdown(u);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r));
        return ans;
    }
    void pushdown(int u) {
        if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {
            tr[u].ls = ++cnt;
            tr[tr[u].ls] = new Node();
        }
        if (tr[u].rs == 0) {
            tr[u].rs = ++cnt;
            tr[tr[u].rs] = new Node();
        }
        if (tr[u].add == 0) return ;
        int add = tr[u].add;
        tr[tr[u].ls].add = add; tr[tr[u].rs].add = add;
        tr[tr[u].ls].val = add; tr[tr[u].rs].val = add;
        tr[u].add = 0;
    }
    void pushup(int u) {
        tr[u].val = Math.max(tr[tr[u].ls].val, tr[tr[u].rs].val);
    }
    public List<Integer> fallingSquares(int[][] ps) {
        List<Integer> ans = new ArrayList<>();
        tr[1] = new Node();
        for (int[] info : ps) {
            int x = info[0], h = info[1], cur = query(1, 1, N, x, x + h - 1);
            update(1, 1, N, x, x + h - 1, cur + h);
            ans.add(tr[1].val);
        }
        return ans;
    }
}
  • 时间复杂度：令 mmm 为查询次数，nnn 为值域大小，复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)
  • 空间复杂度：O(mlog⁡n)O(m\log{n})O(mlogn)

线段树（动态开点 - 动态指针）

利用「动态指针」实现的「动态开点」可以有效避免数组估点问题，更重要的是可以有效避免 new 大数组的初始化开销，对于 LC 这种还跟你算所有样例总时长的 OJ 来说，在不考虑 static 优化/全局数组优化 的情况下，动态指针的方式要比估点的方式来得好。

代码：

class Solution {
    int N = (int)1e9;
    class Node {
        // ls 和 rs 分别代表当前区间的左右子节点
        Node ls, rs;
        // val 代表当前区间的最大高度，add 为懒标记
        int val, add;
    }
    Node root = new Node();
    void update(Node node, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            node.add = v;
            node.val = v;
            return ;
        }
        pushdown(node);
        int mid = lc + rc >> 1;
        if (l <= mid) update(node.ls, lc, mid, l, r, v);
        if (r > mid) update(node.rs, mid + 1, rc, l, r, v);
        pushup(node);
    }
    int query(Node node, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return node.val;
        pushdown(node);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(node.ls, lc, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(node.rs, mid + 1, rc, l, r));
        return ans;
    }
    void pushdown(Node node) {
        if (node.ls == null) node.ls = new Node();
        if (node.rs == null) node.rs = new Node();
        if (node.add == 0) return ;
        node.ls.add = node.add; node.rs.add = node.add;
        node.ls.val = node.add; node.rs.val = node.add;
        node.add = 0;
    }
    void pushup(Node node) {
        node.val = Math.max(node.ls.val, node.rs.val);
    }
    public List<Integer> fallingSquares(int[][] ps) {
        List<Integer> ans = new ArrayList<>();
        for (int[] info : ps) {
            int x = info[0], h = info[1], cur = query(root, 0, N, x, x + h - 1);
            update(root, 0, N, x, x + h - 1, cur + h);
            ans.add(root.val);
        }
        return ans;
    }
}
  • 时间复杂度：令 mmm 为查询次数，nnn 为值域大小，复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)
  • 空间复杂度：O(mlog⁡n)O(m\log{n})O(mlogn)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.699 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

转载自:https://juejin.cn/post/7102072293844582407
评论
请登录