391. 完美矩形
难度 困难
给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。
示例 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：
输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]] 输出：false 解释：两个矩形之间有间隔，无法覆盖成一个矩形。
示例 3：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]] 输出：false 解释：图形顶端留有空缺，无法覆盖成一个矩形。
示例 4：
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]] 输出：false 解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
提示：
- 1 <= rectangles.length <= 2 * 104
- rectangles[i].length == 4
- -105 <= xi, yi, ai, bi <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
思路:数学 把所有矩形的面积和求出来 和覆盖的区域矩形面积比较 相等 精确覆盖 大于 中间有相交区域 小于 留有空缺
class Solution { public boolean isRectangleCover(int[][] rectangles) { int minx=rectangles[0][0],miny=rectangles[0][1],maxa=rectangles[0][2],maxb=rectangles[0][3]; int area=0; for (int [] r:rectangles){ area+=area(r); if(r[0]<minx){ minx=r[0]; } if(r[1]<miny){ miny=r[1]; } if(r[2]>maxa){ maxa=r[2]; } if(r[3]>maxb){ maxb=r[3]; } } int a=(maxa-minx)*(maxb-miny); return a==area; } public int area(int[] r){ return (r[2]-r[0])*(r[3]-r[1]); } }
原因是重叠的面积和空余的面积相等
思路：交集 可以先把重叠的情况排除了
官方
方法一：哈希表
精确覆盖意味着：
- 矩形区域中不能有空缺，即矩形区域的面积等于所有矩形的面积之和；
- 矩形区域中不能有相交区域。
我们需要一个统计量来判定是否存在相交区域。由于精确覆盖意味着矩形的边和顶点会重合在一起，我们不妨统计每个矩形顶点的出现次数。同一个位置至多只能存在四个顶点，在满足该条件的前提下，如果矩形区域中有相交区域，这要么导致矩形区域四角的顶点出现不止一次，要么导致非四角的顶点存在出现一次或三次的顶点；
因此要满足精确覆盖，除了要满足矩形区域的面积等于所有矩形的面积之和，还要满足矩形区域四角的顶点只能出现一次，且其余顶点的出现次数只能是两次或四次。
在代码实现时，我们可以遍历矩形数组，计算矩形区域四个顶点的位置，以及矩形面积之和，并用哈希表统计每个矩形的顶点的出现次数。遍历完成后，检查矩形区域的面积是否等于所有矩形的面积之和，以及每个顶点的出现次数是否满足上述要求。
class Solution { public boolean isRectangleCover(int[][] rectangles) { long area = 0; int minX = rectangles[0][0], minY = rectangles[0][1], maxX = rectangles[0][2], maxY = rectangles[0][3]; Map<Point, Integer> cnt = new HashMap<Point, Integer>(); for (int[] rect : rectangles) { int x = rect[0], y = rect[1], a = rect[2], b = rect[3]; area += (long) (a - x) * (b - y); minX = Math.min(minX, x); minY = Math.min(minY, y); maxX = Math.max(maxX, a); maxY = Math.max(maxY, b); Point point1 = new Point(x, y); Point point2 = new Point(x, b); Point point3 = new Point(a, y); Point point4 = new Point(a, b); cnt.put(point1, cnt.getOrDefault(point1, 0) + 1); cnt.put(point2, cnt.getOrDefault(point2, 0) + 1); cnt.put(point3, cnt.getOrDefault(point3, 0) + 1); cnt.put(point4, cnt.getOrDefault(point4, 0) + 1); } Point pointMinMin = new Point(minX, minY); Point pointMinMax = new Point(minX, maxY); Point pointMaxMin = new Point(maxX, minY); Point pointMaxMax = new Point(maxX, maxY); if (area != (long) (maxX - minX) * (maxY - minY) || cnt.getOrDefault(pointMinMin, 0) != 1 || cnt.getOrDefault(pointMinMax, 0) != 1 || cnt.getOrDefault(pointMaxMin, 0) != 1 || cnt.getOrDefault(pointMaxMax, 0) != 1) { return false; } cnt.remove(pointMinMin); cnt.remove(pointMinMax); cnt.remove(pointMaxMin); cnt.remove(pointMaxMax); for (Map.Entry<Point, Integer> entry : cnt.entrySet()) { int value = entry.getValue(); if (value != 2 && value != 4) { return false; } } return true; } } class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public int hashCode() { return x + y; } @Override public boolean equals(Object obj) { if (obj instanceof Point) { Point point2 = (Point) obj; return this.x == point2.x && this.y == point2.y; } return false; } }
复杂度分析
- 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{rectangles}rectangles 的长度。
- 空间复杂度：O(n)O(n)。我们需要用哈希表存储矩形的顶点及其出现次数。
作者：LeetCode-Solution
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
