LC 699. 掉落的方块
题目描述
这是 LeetCode 上的 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32输入: [[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:1
2
3
4
5输入: [[100, 100], [200, 100]]
输出: [100, 100]
解释: 相邻的方块不会过早地卡住，只有它们的底部边缘才能粘在表面上。
注意:
- $1 <= positions.length <= 1000$
- $1 <= positions[i][0] <= 10^8$
- $1 <= positions[i][1] <= 10^6$
基本分析
为了方便，我们使用 ps 来代指 positions。
每次从插入操作都附带一次询问，因此询问次数为 $1e3$，左端点的最大值为 $10e8$，边长最大值为 $1e6$，由此可知值域范围大于 $1e8$，但不超过 $1e9$。
对于值域范围大，但查询次数有限的区间和问题，不久前曾经总结过 : 求解常见「值域爆炸，查询有限」区间问题的几种方式，可作为前置 🧀 进行了解。
而我的个人习惯，一般要么使用「离散化 + 线段树」，要么使用「线段树（动态开点）」进行求解。
本题为「非强制在线」问题，因此可以先对 ps 数组进行离散化，将值域映射到较小的空间，然后套用固定占用 $4 \times n$ 空间的线段树求解。
但更为灵活（能够同时应对强制在线问题）的求解方式是「线段树（动态开点）」。
同时实现动态开点的方式有两种：
- 根据操作次数对使用到的最大点数进行预估，并采用数组方式进行实现线段树（解法一）；
- 使用动态指针（解法二）；
方式一在不久之前的每日一题 933. 最近的请求次数 讲过，因此今天把方式二也写一下。
具体的，我们将顺序放置方块的操作（假设当前方块的左端点为 $a$，边长为 $len$，则有右端点为 $b = a + len$），分成如下两步进行：
- 查询当前范围 $[a, b]$ 的最大高度为多少，假设为 $cur$；
- 更新当前范围 $[a, b]$ 的最新高度为 $cur + len$。
因此这本质上是一个「区间修改 + 区间查询」的问题，我们需要实现带「懒标记」的线段树，从而确保在进行「区间修改」时复杂度仍为 $O(\log{n})$。
另外有一个需要注意的细节是：不同方块之间的边缘可以重合，但不会导致方块叠加，因此我们当我们对一个区间 $[a, b]$ 进行操作（查询或插入）时，可以将其调整为 $[a, b - 1]$，从而解决边缘叠加操作高度错误的问题。
线段树（动态开点 - 估点）
估点的基本方式在前置 🧀 求解常见「值域爆炸，查询有限」区间问题的几种方式 详细讲过。
简单来说，可以直接估算为 $6 \times m \times \log{n}$ 即可，其中 $m$ 为询问次数（对应本题就是 ps 的长度），而 $n$ 为值域大小（对应本题可直接取成 $1e9$）；而另外一个比较实用（避免估算）的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（不考虑字节对齐，或者结构体过大的情况，Java 的 $128M$ 可以开到 $5 \times 10^6$ 以上）。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58class 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;
}
}
- 时间复杂度：令 $m$ 为查询次数，$n$ 为值域大小，复杂度为 $O(m\log{n})$
- 空间复杂度：$O(m\log{n})$
线段树（动态开点 - 动态指针）
利用「动态指针」实现的「动态开点」可以有效避免数组估点问题，更重要的是可以有效避免 new 大数组的初始化开销，对于 LC 这种还跟你算所有样例总时长的 OJ 来说，在不考虑 static 优化/全局数组优化 的情况下，动态指针的方式要比估点的方式来得好。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class 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;
}
}
- 时间复杂度：令 $m$ 为查询次数，$n$ 为值域大小，复杂度为 $O(m\log{n})$
- 空间复杂度：$O(m\log{n})$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.699 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
