391.完美矩形，如果用扫描线算法你会怎么做
- 2020 年 3 月 11 日
- 筆記
题目描述
我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如， 一个单位正方形可以表示为 [1,1,2,2]。( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。
示例 1
示例 1:
rectangles = [ [1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4] ] 返回 true。5个矩形一起可以精确地覆盖一个矩形区域。
'◡'
示例 2
示例 2:
rectangles = [ [1,1,2,3], [1,3,2,4], [3,1,4,2], [3,2,4,4] ] 返回 false。两个矩形之间有间隔，无法覆盖成一个矩形。
'◡'
示例 3
示例 3:
rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [3,2,4,4] ] 返回 false。图形顶端留有间隔，无法覆盖成一个矩形。
'◡'
示例 4
示例 4:
rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [2,2,4,4] ] 返回 false。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
解题
这道题的题目标签是扫描线算法，那我们就按扫描线算法把这道题倒出来。
先简单介绍扫描线算法，扫描线平行于任一坐标轴扫过平面，随着坐标轴的变量而移动，变量的变化方向可负可正。意思是既可以从左到右扫描，也可以从右到左扫描；既可以从上到下扫描，也可以从下到上扫描。
所以俺这里就采用平行于y轴，从左到右扫描坐标图。
然后，再看输入示例，比如是这样的 [1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4] , 我们可以把它设定成下面这样的：
每个矩形的两个关键点
俺选中了每个矩形的左下和右下的两个端点，当然也可以选每个矩形的左上和右上的两个端点。
因为我们得到的红黑端点是乱序的，要给它先按x轴排序。
注意，如果两个端点的横坐标相等，我们要先判断红黑色点，如果是黑色点就排前面，如果是红色点就排后面，相等于就给它们分组了。不过黑色点和红色点怎么分组呢？
我们可以把黑色点的高度变成负数，红色点的高度还是原值，这样就可以分组了，同时也为后面的出入堆进行了有利的判断。
如果在同一横坐标有多个黑色点的话，就按照y轴排序，另一组的红色点也是。
如果某编程语言的数据结构有可重复且有序的集合的话，可以采用这个集合；如果没有，就想办法实现。
在Java没有这样的集合，但是可以利用TreeSet的Comparator内部类实现，在Comparator内部类重写一个比较方法，其中Triplet保存的是一个红色点或黑色点。
TreeSet<Triplet> triplets = new TreeSet<>((o1, o2) -> { if (o1.x != o2.x) return o1.x - o2.x; if (o1.h * o2.h < 0) return o1.h < 0 ? -1 : 1; // 正数 和 负数要分类，负数在左，正数在右 if (o1.y != o2.y) return o1.y - o2.y; return 1; // 保证重复且有序 ，例如这个用例：[[0,0,4,1],[0,0,4,1]] });
这样，triplets就按照要求已经排好序了。
然后进行扫描线的移动，移到第一个矩形的左边界的时候，我们要到这个高度入堆。同时将这同一横坐标的高度全部入堆，然后把堆里的高度全部累加起来，得到一个临时高度。如果临时高度和投影高度不一致的话，则可以直接返回false。
投影
同时，同时也可以创建投影的上界和下界，只要是超出这个范围，那是不满足完美矩形的，可以直接返回false。
我们还要注意临时上界，如果下一个红色点的纵坐标要小于临时上界的话，也可以直接返回flase。
临时上界
如果临时上界等于下一红色点的纵坐标的话，则说明这两个矩形是没有覆盖的，接着将临时上界更新为该横坐标最高的高度。
如果扫描线在不同的横坐标，遇到第一个黑色点的话，则将临时上界更新为该横坐标第一个黑色点的纵坐标，从最低处开始。
依次类推，直到坐标图上矩形的最右边界，这个边界可以不用判断了，因为最右边界的上一边界是满足的，而且每一个都是矩形，左边界满足，右边界如果没有新的矩形的话自然也会满足，所以判断到最右边界还没有返回false，则可以直接返回true。
动画：扫描线移动过程
视频大小：1.15M，比Gif格式要小，可放心看
Java代码，从左到右扫描
import java.util.*; class Solution { private class Triplet { int x; int y; int h; Triplet(int x, int y, int h) { this.x = x; this.y = y; this.h = h; } } public boolean isRectangleCover(int[][] rectangles) { // 左上角 右下角坐标 // 将 rectangles 转换 三元组 [x y h] TreeSet<Triplet> triplets = new TreeSet<>((o1, o2) -> { if (o1.x != o2.x) return o1.x - o2.x; if (o1.h * o2.h < 0) return o1.h < 0 ? -1 : 1; // 正数 和 负数要分类，负数在左，正数在右 if (o1.y != o2.y) return o1.y - o2.y; return 1; // 保证重复且有序 ，例如这个用例：[[0,0,4,1],[0,0,4,1]] }); for (int[] rectangle : rectangles) { triplets.add(new Triplet(rectangle[0], rectangle[1], rectangle[3] - rectangle[1])); // 左端点的高度为正 triplets.add(new Triplet(rectangle[2], rectangle[1], rectangle[1] - rectangle[3])); // 右端点的高度为负 } // 创建优先队列 Queue<Integer> queue = new PriorityQueue<>(); // 边界上下 宽度 int high = 0, low = 0, width = 0; // 记录横坐标的变化 int axis = triplets.first().x; // 以第一个左边界作为标准 low = triplets.first().y; for (Triplet triplet : triplets) { if (axis == triplet.x) { high = triplet.y + triplet.h; } else break; } width = high - low; // 临时宽度; 临时上界 int cur_w = 0, cur_h = Integer.MIN_VALUE; // 正数入堆 负数出堆 for (Triplet triplet : triplets) { // 判断 是否出界 if (triplet.x < low) return false; if (triplet.y + triplet.h > high) return false; if (axis != triplet.x) { if (cur_w != width) return false; cur_h = triplet.y; axis = triplet.x; } else if (triplet.y < cur_h) { return false; } if (triplet.h > 0) cur_h = triplet.y + triplet.h; if (triplet.h > 0) queue.add(triplet.h); else if (triplet.h < 0) queue.remove(-triplet.h); cur_w += triplet.h; } return true; } }
Java代码，从下到上扫描
public boolean isRectangleCover(int[][] rectangles) { TreeSet<Triplet> triplets = new TreeSet<>((o1, o2) -> { if (o1.y != o2.y) return o1.y - o2.y; if (o1.h * o2.h < 0) return o1.h < 0 ? -1 : 1; // 正数 和 负数要分类，负数在左，正数在右 if (o1.x != o2.x) return o1.x - o2.x; return 1; // 保证重复且有序 ，例如这个用例：[[0,0,4,1],[0,0,4,1]] }); for (int[] rectangle : rectangles) { triplets.add(new Triplet(rectangle[0], rectangle[1], rectangle[2] - rectangle[0])); // 左端点的高度为正 triplets.add(new Triplet(rectangle[0], rectangle[3], rectangle[0] - rectangle[2])); // 右端点的高度为负 } // 创建优先队列 Queue<Integer> queue = new PriorityQueue<>(); int l = 0, r = 0, width = 0; // 记录纵坐标的变化 int axis = triplets.first().y; l = triplets.first().x; for (Triplet triplet : triplets) { if (axis == triplet.y) { r = triplet.x + triplet.h; } else break; } width = r - l; int cur_w = 0, cur_len = Integer.MIN_VALUE; // 正数入堆 负数出堆 for (Triplet triplet : triplets) { // 判断 是否出界 if (triplet.x < l) return false; if (triplet.x + triplet.h > r) return false; if (axis != triplet.y) { if (cur_w != width) return false; cur_len = triplet.x; axis = triplet.y; } else if (triplet.x < cur_len) { return false; } if (triplet.h > 0) cur_len = triplet.x + triplet.h; if (triplet.h > 0) queue.add(triplet.h); else if (triplet.h < 0) queue.remove(-triplet.h); cur_w += triplet.h; } return true; }
