LeetCode动画 | 699.掉落的方块
- 2020 年 3 月 11 日
- 筆記
这篇文章写着写着，篇幅就变得有点长了，但是这对你很有帮助，因为我在写Java代码过程中进行了两步优化，过程都写下来了。
后面也会贴Go语言代码，记得收哦，简单对比了Java和Go语言的执行分析，对学习Go语言有好处的。
题目描述
在无限长的数轴（即 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.
解题
还是老样子，不管是先看题目描述还是先看题目标签，都可随意安排。
因为我是先选了线段树的标签，然后随机选一个题看看，这样子先看题目标签再看题目描述，没毛病！
想到线段树，自然会想到它的框架，先分治再合并。不过这道题，可不是先分支再合并这么简单了。
我们看完题目描述之后，假设输入示例是这样的 {{5, 2}, {6, 1}, {4, 1}, {2, 3}} ，按照线段树的框架，自然会变成下面这样的：
分治
我们得到的树底下的节点之后，怎么拆分是一个问题，怎么合并也是一个问题。
例如我们得到 {5，2}这个节点，可以设计成 {5，7，2}，分别是左边界、右边界和高度，不过我们设计的高度是向下的，如下面图：
一个方块
通过左递归得到{5，2}这个节点，变换成{5，7，2}；通过右递归得到{6，1}这个节点，变换成{6，7，1}；接着进行合并，这个问题就来了，怎么合并也是一个问题。
或许我们可以设计成下面这样：
方块表示
因为，题目要求掉落的方块是有顺序性的，不可能随机掉落哪个方块仍然答案是唯一的。所以我们按照了每个节点的左边界进行比较。
如果这个节点的左边界比根节点左边界小的话，那这个节点往根节点的左孩子递归；反之这个节点往根节点的右孩子递归；到下一个孩子节点也是这样比较和递归。
最后，我们得到了这样的一个图：
假设合并成这样
最关键的一点来了，接着上面的图，这两个子集合并应该怎样进行呢？
因为我们要保证方块掉落的顺序，右边子集的根节点要先和左边子集的根节点比较和递归，变成下面这样的：
顺序性和比较性
而且从上面的图可以翻译成下面这样的：
方块掉落
这已经涉及到图论建模了，这图不管是进行深度遍历还是广度遍历总会找到目前区间的最高的高度。
但是这已经不符合线段树的优化了，我们知道线段树可以分治吧，分治的目的是降低时间复杂度。
你看，如果掉落的方块变成下面这样的，如果要找到区间【7，8】，就只能通过深度遍历或广度遍历才能找到这区间的最高高度为3。
图论建模
如果我们把图论建模成下面这样的：
换一个方式
再复杂点，就变成下面这样的，如果找到【3，5】，遍历的时候可以判断是否满足r <= root.l这个条件，如果满足，就没必要递归这个节点的右孩子了，因为5根本就不可能跑到5后面的坐标，所以我在这个地方进行了剪枝操作，待会看后面代码会有注释。
图论建模
所以，我们本来想通过线段树的思路解决此题，到最后变成了图论建模。如果这道题是单纯的使用线段树，忘记了分治算法的优点的话，时间复杂度并没有O(log n)这样的，仍需要全部遍历才能找到这个区间的最高高度。
所以，在这道题上，我们先还是按顺序一个一个进行合并，如前面两个合并，第三个和前面合并，第四个和前面合并，依次类推。
既然线段树变成图论建模这地步了，我们就按着图论建模继续优化吧。
我们知道，我把这每一个节点定义成{左边界，右边界，高度}，每一次将节点放置的时候是不是先要获取这个区间的最高高度。
如果我们提前知道最有边界是多少，下一个方块的左边界要是比最有边界大的话，是不是直接获取0了，如下面这样的：
降落
所以，我们可以把方块定义成{l，r，h，maxR}，其中maxR表示目前最优边界。这样下一个节点降落的时候直接跟根节点的maxR比较，如果下一节点的左边界要大于等于maxR的话，可以直接获得这个区间的高度为 0。
最后，按照这个思路使用Java编写逻辑，执行用时也完胜100%的用户：
执行用时 : 6 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗 : 41.2 MB , 在所有 Java 提交中击败了 25.00% 的用户
而使用Go语言也一样。
执行用时 : 12 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗 : 5.6 MB , 在所有 Go 提交中击败了 100.00% 的用户
从执行结果上看，Go语言执行用时比Java耗时一点，但是内存消耗却比Java要少很多。
Java代码第一版本，未优化
import java.util.*; class Solution { // 描述方块以及高度 private class Node { int l, r, h; Node left, right; public Node(int l, int r, int h) { this.l = l; this.r = r; this.h = h; 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); if (l <= root.l) root.left = insert(root.left, l, r, h); else root.right = insert(root.right, l, r, h); return root; // 返回根节点 } private int query(Node root, int l, int r) { if (root == null) return 0; // 高度 int curH = 0; if (!(r <= root.l || root.r <= l)) // 是否跟这个节点相交 curH = root.h; // 未剪枝 curH = Math.max(curH, query(root.left, l, r)); curH = Math.max(curH, query(root.right, l, r)); return curH; } }
执行结果
执行用时 : 48 ms , 在所有 Java 提交中击败了 20.59% 的用户 内存消耗 : 40.9 MB , 在所有 Java 提交中击败了 25.00% 的用户
Java代码第二版本，剪枝
import java.util.*; class Solution { // 描述方块以及高度 private class Node { int l, r, h; Node left, right; public Node(int l, int r, int h) { this.l = l; this.r = r; this.h = h; 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); if (l <= root.l) root.left = insert(root.left, l, r, h); else root.right = insert(root.right, l, r, h); return root; // 返回根节点 } private int query(Node root, int l, int r) { if (root == null) 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; } }
剪枝后执行结果
执行用时 : 24 ms , 在所有 Java 提交中击败了 91.18% 的用户 内存消耗 : 41.1 MB , 在所有 Java 提交中击败了 25.00% 的用户
剪枝后提升了百分之56%多，进步蛮明显的。
Java代码最终优化
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; } }
执行结果
执行用时 : 6 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗 : 41.2 MB , 在所有 Java 提交中击败了 25.00% 的用户
Go语言代码，对应Java最终优化版本
import ( "fmt" ) // 定义方块的结构体 type Node struct { l, r, h, maxR int left, right *Node // 指针类型，难难难（大学没学好C语言的后果，一不小心bu会用） } func fallingSquares(positions [][]int) []int { // 创建返回值 使用切片 (动态数组) var res = make([]int, 0) // 根节点 var root *Node = new(Node) // 初始化，对应类型的零值 // 目前最高的高度 maxH := 0 for _, position := range positions { l := position[0] // 左横坐标 r := position[0] + position[1] // 右横坐标 e := position[1] // 边长 curH := query(root, l, r) // 目前区间的最高的高度 root = insert(root, l, r, curH+e) maxH = max(maxH, curH+e) res = append(res, maxH) } return res } func insert(root *Node, l int, r int, h int) *Node { if root == nil { return &Node{ l: l, r: r, h: h, maxR: r, } } if l <= root.l { root.left = insert(root.left, l, r, h) } else { root.right = insert(root.right, l, r, h) } root.maxR = max(r, root.maxR) return root } func query(root *Node, l int, r int) int { // reflect.ValueOf(root).IsValid() 表示判断root是否为空 // 新节点的左边界大于等于目前的maxR的话，直接得到0，不需要遍历了 if root == nil || l >= root.maxR { return 0 } // 高度 curH := 0 if !(r <= root.l || root.r <= l) { // 是否跟这个节点相交 curH = root.h } // 剪枝 curH = max(curH, query(root.left, l, r)) if r >= root.l { curH = max(curH, query(root.right, l, r)) } return curH } func max(l, r int) int { if l > r { return l } return r }
执行结果
执行用时 : 12 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗 : 5.6 MB , 在所有 Go 提交中击败了 100.00% 的用户
