宫水三叶的刷题日记

V1

2022/06/18阅读:14主题:前端之巅同款

【宫水三叶的刷题日记】699. 掉落的方块(困难)

题目描述

这是 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]

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

注意:

基本分析

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

每次从插入操作都附带一次询问,因此询问次数为 ,左端点的最大值为 ,边长最大值为 ,由此可知值域范围大于 ,但不超过

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

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

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

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

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

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

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

具体的,我们将顺序放置方块的操作(假设当前方块的左端点为 ,边长为 ,则有右端点为 ),分成如下两步进行:

  • 查询当前范围 的最大高度为多少,假设为
  • 更新当前范围 的最新高度为

因此这本质上是一个「区间修改 + 区间查询」的问题,我们需要实现带「懒标记」的线段树,从而确保在进行「区间修改」时复杂度仍为

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

线段树(动态开点 - 估点)

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

简单来说,可以直接估算为 即可,其中 为询问次数(对应本题就是 ps 的长度),而 为值域大小(对应本题可直接取成 );而另外一个比较实用(避免估算)的估点方式可以「尽可能的多开点数」,利用题目给定的空间上界和我们创建的自定义类(结构体)的大小,尽可能的多开(不考虑字节对齐,或者结构体过大的情况,Java 可以开到 以上)。

代码:

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 == 0return ;
        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(11, N, x, x + h - 1);
            update(11, N, x, x + h - 1, cur + h);
            ans.add(tr[1].val);
        }
        return ans;
    }
}
  • 时间复杂度:令 为查询次数, 为值域大小,复杂度为
  • 空间复杂度:

线段树(动态开点 - 动态指针)

利用「动态指针」实现的「动态开点」可以有效避免数组估点问题,更重要的是可以有效避免 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 == 0return ;
        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;
    }
}
  • 时间复杂度:令 为查询次数, 为值域大小,复杂度为
  • 空间复杂度:

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

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

分类:

后端

标签:

数据结构与算法

作者介绍

宫水三叶的刷题日记
V1