LeetCode刷题-完美矩形
前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给你一个数组rectangles，其中rectangles[i] = [xi, yi, ai, bi]表示一个坐标轴平行的矩形。这个矩形的左下顶点是(xi, yi)，右上顶点是(ai, bi)。
如果所有矩形一起精确覆盖了某个矩形区域，则返回true；否则，返回false。
示例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
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
提示：
1 <= rectangles.length <= 2 * 10^4
rectangles[i].length == 4
-10^5 <= xi, yi, ai, bi <= 10^5
分析过程
思路：计算总面积是否相等，四个最顶点只出现一次，其他点只出现两次或四次，即满足以下两个条件。
条件1：计算小矩形面积之和，计算大矩形面积，判断小矩形面积之和是否等于大矩形面积。
条件2：最左下、最左上、最右下、最右上的四个点只出现一次，其他点成对出现，即只出现2次或者4次。
分析：
从上面的四个示例，可以很容易看出，小矩形面积之和必须先要等于大矩形面积。
如何理解最左下、最左上、最右下、最右上的四个点只出现一次？可以举出一个反例，小矩形面积之和等于大矩形面积，但是最左下、最左上、最右下、最右上的四个点并没有只出现一次，注意是只出现一次，出现零次和两次以上都是不行的，如图：
图5
输入：rectangles = [[0,0,2,1],[1,0,2,2]]
大矩形面积是2 * 2 = 4，小矩形面积之和是2 * 1 + 1 * 2 = 4，小矩形面积之和等于大矩形面积，但是并不是完美矩形，因为并没有精确覆盖了某个矩形区域，有重叠交叉的地方，而这里的最左下、最左上、最右下、最右上的四个点并不是只出现一次的，最左上顶点(0,2)出现零次。
如何理解其他点成对出现，即只出现两次或者四次？同样可以举出一个反例，小矩形面积之和等于大矩形面积，同时最左下、最左上、最右下、最右上的四个点只出现一次，但是其他点并没有成对出现，如图：
图6
输入：rectangles = [[0,0,2,2],[1,1,3,3],[2,0,3,1],[0,3,3,4]]
大矩形面积是3 * 4 = 12，小矩形面积之和是2 * 2 + 2 * 2 + 1 * 1 + 3 * 1 = 12，小矩形面积之和等于大矩形面积，最左下、最左上、最右下、最右上的四个点也只出现一次，分别为(0,0)，(0,4)，(3,0)，(3,4)，但是并不是完美矩形，因为并没有精确覆盖了某个矩形区域，有重叠交叉的地方，而这里的其他点并没有成对出现，例如：(0,2)只出现了一次。
可以想象，如果是精确覆盖了某个矩形区域，那么没有相交的区域，只有刚好紧挨的点，如图：
图7
如果是两个矩形区域紧挨，那么公共点刚好就属于两个矩形，出现两次；如果是四个矩形区域紧挨，那么公共点刚好就属于四个矩形，出现四次；因为是精确覆盖矩形区域，所以不会是三个矩形区域，所以从这里可以看出，其他点只出现两次或者四次。
第一步
定义小矩形面积之和sum，初始为0。
定义最左下横坐标minX，初始为第一个矩形的第一个顶点。
定义最左下纵坐标minY，初始为第一个矩形的第二个顶点。
定义最右上横坐标maxX，初始为第一个矩形的第三个顶点。
定义最右上纵坐标maxY，初始为第一个矩形的第四个顶点。
第二步
遍历输入的小矩形列表rectangles，计算小矩形面积之和sum。
每次遍历时：
小矩形长度 = ai - xi。
小矩形宽度 = bi - yi。
累加计算小矩形面积之和sum，小矩形面积之和 = 小矩形长度 * 小矩形宽度。
xi和最左下横坐标minX比较，yi和最左下纵坐标minY比较，更新最左下横坐标minX和最左下纵坐标minY，即更新最左下顶点。
ai和最右上横坐标maxX比较，bi和最右上纵坐标maxY比较，更新最左下横坐标minX和最左下纵坐标minY，即更新最右上顶点。
遍历结束，计算大矩形面积area。
大矩形面积 = 大矩形长度 * 大矩形宽度 = (最右上横坐标 - 最左下横坐标) * (最右上纵坐标 - 最左下纵坐标) = (maxX - minX) * (maxY - minY)。
第三步
若小矩形面积之和sum等于大矩形面积area，判断最左下、最左上、最右下、最右上的四个点是否只出现一次，以及判断其他点是否成对出现，即只出现两次或者四次，否则，不满足完美矩形条件，直接返回false。
第四步
在判断最左下、最左上、最右下、最右上的四个点是否只出现一次，以及判断其他点是否成对出现时：
定义最左下坐标数量leftBottomCount，初始为0。
定义最左上坐标数量leftTopCount，初始为0。
定义最右下坐标数量rightBottomCount，初始为0。
定义最右上坐标数量rightTopCount，初始为0。
定义集合map，用来保存非最顶点坐标的数量。
再次遍历输入的小矩形列表rectangles，每次遍历时：
由于上面已找出上下左右四个最顶点，所以可以判断出每一个小矩形的四个顶点是否为最顶点。
若是最顶点，对应的方向最顶点坐标数量加1，若最顶点数量有出现超过一次，直接返回false。
若不是最顶点，那就是非最顶点，用集合map来记录他们的数量，map的key值用横坐标-纵坐标的形式来表示。
遍历输入的小矩形列表rectangles结束后，遍历集合map，用来判断非最顶点坐标的数量是否都是成对出现，即数量是否都为2或4。
第五步
每次遍历集合map时：
若有非最顶点坐标的数量不等于2或4，直接返回false。
遍历集合map结束后，判断最左下、最左上、最右下、最右上的四个点是否只出现一次，若都只出现一次，返回true，否则返回false。
解答代码
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
// 条件1：计算小矩形面积之和，计算大矩形面积，判断小矩形面积之和是否等于大矩形面积
// 条件2：最左下、最左上、最右下、最右上的四个点只出现一次，其他点成对出现，即只出现两次或者四次
// 小矩形面积之和
int sum = 0;
// 最左下横坐标
int minX = rectangles[0][0];
// 最左下纵坐标
int minY = rectangles[0][1];
// 最右上横坐标
int maxX = rectangles[0][2];
// 最右上纵坐标
int maxY = rectangles[0][3];
// 遍历小矩形
for (int[] rectangle : rectangles) {
// 小矩形长度
int length = rectangle[2] - rectangle[0];
// 小矩形宽度
int width = rectangle[3] - rectangle[1];
// 累加计算小矩形面积之和
sum += length * width;
if (rectangle[0] <= minX && rectangle[1] <= minY) {
// 更新最左下横坐标
minX = rectangle[0];
// 更新最左下纵坐标
minY = rectangle[1];
}
if (rectangle[2] >= maxX && rectangle[3] >= maxY) {
// 更新最右上横坐标
maxX = rectangle[2];
// 更新最右上纵坐标
maxY = rectangle[3];
}
}
// 计算大矩形面积
int area = (maxX - minX) * (maxY - minY);
if (sum == area) {
// 若小矩形面积之和等于大矩形面积，判断最左下、最左上、最右下、最右上的四个点是否只出现一次
// 最左下坐标数量
int leftBottomCount = 0;
// 最左上坐标数量
int leftTopCount = 0;
// 最右下坐标数量
int rightBottomCount = 0;
// 最右上坐标数量
int rightTopCount = 0;
// 定义集合，保存非最顶点坐标的数量
Map<String, Integer> map = new HashMap<>();
// 再次遍历小矩形
for (int[] rectangle : rectangles) {
if (rectangle[0] == minX && rectangle[1] == minY) {
// 最左下坐标数量加1
++leftBottomCount;
if (leftBottomCount > 1) {
// 若最左下坐标数量大于1，直接返回false
return false;
}
} else {
// 若不是最左下坐标，更新集合中非最顶点坐标的数量
String lb = rectangle[0] + "-" + rectangle[1];
map.put(lb, map.getOrDefault(lb, 0) + 1);
}
if (rectangle[0] == minX && rectangle[3] == maxY) {
// 最左上坐标数量加1
++leftTopCount;
if (leftTopCount > 1) {
// 若最左上坐标数量大于1，直接返回false
return false;
}
} else {
// 若不是最左上坐标，更新集合中非最顶点坐标的数量
String lt = rectangle[0] + "-" + rectangle[3];
map.put(lt, map.getOrDefault(lt, 0) + 1);
}
if (rectangle[2] == maxX && rectangle[1] == minY) {
// 最右下坐标数量加1
++rightBottomCount;
if (rightBottomCount > 1) {
// 若最右下坐标数量大于1，直接返回false
return false;
}
} else {
// 若不是最右下坐标，更新集合中非最顶点坐标的数量
String rb = rectangle[2] + "-" + rectangle[1];
map.put(rb, map.getOrDefault(rb, 0) + 1);
}
if (rectangle[2] == maxX && rectangle[3] == maxY) {
// 最右上坐标数量加1
++rightTopCount;
if (rightTopCount > 1) {
// 若最右上坐标数量大于1，直接返回false
return false;
}
} else {
// 若不是最右上坐标，更新集合中非最顶点坐标的数量
String rt = rectangle[2] + "-" + rectangle[3];
map.put(rt, map.getOrDefault(rt, 0) + 1);
}
}
// 遍历集合，判断非最顶点坐标的数量是否都是成对出现，即数量是否都为2或4
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() != 2 && entry.getValue() != 4) {
// 若有非最顶点坐标的数量不等于2或4，返回false
return false;
}
}
// 若最左下、最左上、最右下、最右上的四个点只出现一次，返回true
return leftBottomCount == 1 && leftTopCount == 1 && rightBottomCount == 1 && rightTopCount == 1;
}
// 若小矩形面积之和不等于大矩形面积，直接返回false
return false;
}
}
提交结果
执行用时46ms，时间击败57.21%的用户，内存消耗47.6MB，空间击败18.97%的用户。
运行结果
原文链接
原文链接：完美矩形
