当前位置：首页 > news >正文

LeetCode 391：完美矩形

news 2025/7/27 14:45:01

LeetCode 391：完美矩形

在这里插入图片描述

问题本质：精确覆盖的两个核心条件

给定若干轴对齐的小矩形，判断它们是否能恰好覆盖一个大矩形（无重叠、无间隙）。需满足：

面积守恒：所有小矩形的面积和等于大矩形的面积。
顶点唯一：除大矩形的4个顶点外，其他顶点必须出现偶数次（重叠时顶点会被覆盖两次，间隙则会导致顶点缺失）。

核心思路：面积 + 顶点统计

1. 面积校验

遍历所有小矩形，计算 大矩形的边界（最小左边界 left、最小下边界 bottom、最大右边界 right、最大上边界 top）。
计算 小矩形总面积 和 大矩形面积，若不相等，直接返回 false（存在间隙）。

2. 顶点校验

用哈希表统计所有小矩形的 4个顶点（左下、左上、右下、右上）的出现次数。
大矩形的4个顶点必须仅出现1次（唯一角），其余顶点必须出现偶数次（重叠抵消）。

算法步骤详解

步骤 1：计算大矩形边界与面积

int left = Integer.MAX_VALUE;   // 初始为极大值，确保被更新
int bottom = Integer.MAX_VALUE; 
int right = Integer.MIN_VALUE;  // 初始为极小值，确保被更新
int top = Integer.MIN_VALUE;    
long sumArea = 0;               // 小矩形总面积for (int[] rect : rectangles) {int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];// 更新大矩形边界left = Math.min(left, x1);bottom = Math.min(bottom, y1);right = Math.max(right, x2);top = Math.max(top, y2);// 累加小矩形面积sumArea += (long)(x2 - x1) * (y2 - y1);
}// 大矩形面积
long totalArea = (long)(right - left) * (top - bottom);
if (sumArea != totalArea) {return false; // 面积不等，直接失败
}

步骤 2：统计顶点出现次数

用哈希表记录每个顶点的出现次数（顶点用 (x, y) 唯一标识，通过位运算转换为 long 键）：

Map<Long, Integer> pointCount = new HashMap<>();for (int[] rect : rectangles) {int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];// 四个顶点：左下、左上、右下、右上addPoint(pointCount, x1, y1);addPoint(pointCount, x1, y2);addPoint(pointCount, x2, y1);addPoint(pointCount, x2, y2);
}// 辅助方法：将(x,y)转换为唯一long键
private long getKey(int x, int y) {return (long)x << 32 | (y & 0xFFFFFFFFL); // x左移32位，y存低32位
}// 辅助方法：更新顶点计数
private void addPoint(Map<Long, Integer> map, int x, int y) {long key = getKey(x, y);map.put(key, map.getOrDefault(key, 0) + 1);
}

步骤 3：校验顶点规则

大矩形的4个顶点必须仅出现1次：

int[][] corners = {{left, bottom},  // 左下{left, top},     // 左上{right, bottom}, // 右下{right, top}     // 右上
};for (int[] corner : corners) {int x = corner[0], y = corner[1];long key = getKey(x, y);Integer cnt = pointCount.get(key);if (cnt == null || cnt != 1) {return false; // 顶点不存在或次数不对}pointCount.put(key, cnt - 1); // 次数减为0（后续统一校验偶数）
}

所有顶点次数必须为偶数（包括大矩形顶点减为0的情况）：

for (int count : pointCount.values()) {if (count % 2 != 0) {return false; // 存在奇数次顶点，说明重叠或缺失}
}

完整代码（Java）

import java.util.HashMap;
import java.util.Map;class Solution {public boolean isRectangleCover(int[][] rectangles) {if (rectangles == null || rectangles.length == 0) {return false;}// 步骤1：计算大矩形的边界和总面积int left = Integer.MAX_VALUE;int bottom = Integer.MAX_VALUE;int right = Integer.MIN_VALUE;int top = Integer.MIN_VALUE;long sumArea = 0;for (int[] rect : rectangles) {int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];left = Math.min(left, x1);bottom = Math.min(bottom, y1);right = Math.max(right, x2);top = Math.max(top, y2);sumArea += (long)(x2 - x1) * (y2 - y1);}// 校验面积是否相等long totalArea = (long)(right - left) * (top - bottom);if (sumArea != totalArea) {return false;}// 步骤2：统计所有顶点的出现次数Map<Long, Integer> pointCount = new HashMap<>();for (int[] rect : rectangles) {int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];addPoint(pointCount, x1, y1);addPoint(pointCount, x1, y2);addPoint(pointCount, x2, y1);addPoint(pointCount, x2, y2);}// 步骤3：校验大矩形的四个顶点（必须出现1次，然后次数减为0）int[][] corners = {{left, bottom},{left, top},{right, bottom},{right, top}};for (int[] corner : corners) {int x = corner[0], y = corner[1];long key = getKey(x, y);Integer cnt = pointCount.get(key);if (cnt == null || cnt != 1) {return false;}pointCount.put(key, cnt - 1); // 次数减为0}// 步骤4：校验所有顶点的次数是否为偶数for (int count : pointCount.values()) {if (count % 2 != 0) {return false;}}return true;}private long getKey(int x, int y) {return (long)x << 32 | (y & 0xFFFFFFFFL);}private void addPoint(Map<Long, Integer> map, int x, int y) {long key = getKey(x, y);map.put(key, map.getOrDefault(key, 0) + 1);}
}

复杂度分析

时间复杂度：O(n)，n 是小矩形数量。遍历矩形（O(n)）、统计顶点（O(n)，每个矩形4个顶点）、校验顶点（O(n)，顶点数最多为 4n，但哈希表遍历是线性的）。
空间复杂度：O(n)，哈希表最多存储 4n 个顶点（实际远小于，因为大量顶点会重复）。