#

Info

数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
391. Perfect Rectangle	391. 完美矩形	🔴

今天讲一道非常有意思，而且比较有难度的题目。

我们知道一个矩形有四个顶点，但是只要两个顶点的坐标就可以确定一个矩形了（比如左下角和右上角两个顶点坐标）。

今天来看看力扣第 391 题「完美矩形」，题目会给我们输入一个数组 rectangles，里面装着若干四元组 (x1,y1,x2,y2)，每个四元组就是记录一个矩形的左下角和右上角坐标。

也就是说，输入的 rectangles 数组实际上就是很多小矩形，题目要求我们输出一个布尔值，判断这些小矩形能否构成一个「完美矩形」。函数签名如下：

// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

public boolean isRectangleCover(int[][] rectangles) {

// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

bool isRectangleCover(vector<vector<int>>& rectangles)

def isRectangleCover(rectangles: List[List[int]]) -> bool

// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

func isRectangleCover(rectangles [][]int) bool {

// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

function isRectangleCover(rectangles) {
  // function body here
}

所谓「完美矩形」，就是说 rectangles 中的小矩形拼成图形必须是一个大矩形，且大矩形中不能有重叠和空缺。

比如说题目给我们举了几个例子：

这个题目难度是 Hard，如果没有做过类似的题目，还真做不出来。

常规的思路，起码要把最终形成的图形表示出来吧，而且你要有方法去判断两个矩形是否有重叠，是否有空隙，虽然可以做到，不过感觉异常复杂。

其实，想判断最终形成的图形是否是完美矩形，需要从「面积」和「顶点」两个角度来处理。

先说说什么叫从「面积」的角度。

rectangles 数组中每个元素都是一个四元组 (x1, y1, x2, y2)，表示一个小矩形的左下角顶点坐标和右上角顶点坐标。

那么假设这些小矩形最终形成了一个「完美矩形」，你会不会求这个完美矩形的左下角顶点坐标 (X1, Y1) 和右上角顶点的坐标 (X2, Y2)？

这个很简单吧，左下角顶点 (X1, Y1) 就是 rectangles 中所有小矩形中最靠左下角的那个小矩形的左下角顶点；右上角顶点 (X2, Y2) 就是所有小矩形中最靠右上角的那个小矩形的右上角顶点。

注意我们用小写字母表示小矩形的坐标，大写字母表示最终形成的完美矩形的坐标，可以这样写代码：

// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 左下角顶点，初始化为正无穷，以便记录最小值
double X1 = Double.POSITIVE_INFINITY;
double Y1 = Double.POSITIVE_INFINITY;
// 右上角顶点，初始化为负无穷，以便记录最大值
double X2 = Double.NEGATIVE_INFINITY;
double Y2 = Double.NEGATIVE_INFINITY;

for (int i = 0; i < rectangles.length; i++) {
    double x1 = rectangles[i][0];
    double y1 = rectangles[i][1];
    double x2 = rectangles[i][2];
    double y2 = rectangles[i][3];
    // 取小矩形左下角顶点的最小值
    X1 = Math.min(X1, x1);
    Y1 = Math.min(Y1, y1);
    // 取小矩形右上角顶点的最大值
    X2 = Math.max(X2, x2);
    Y2 = Math.max(Y2, y2);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 左下角顶点，初始化为正无穷，以便记录最小值
int X1 = std::numeric_limits<int>::max(), Y1 = std::numeric_limits<int>::max();
// 右上角顶点，初始化为负无穷，以便记录最大值
int X2 = std::numeric_limits<int>::min(), Y2 = std::numeric_limits<int>::min();

for (auto rect : rectangles) {
    // 取小矩形左下角顶点的最小值
    X1 = std::min(X1, rect[0]);
    Y1 = std::min(Y1, rect[1]);
    // 取小矩形右上角顶点的最大值
    X2 = std::max(X2, rect[2]);
    Y2 = std::max(Y2, rect[3]);
}

# 左下角顶点，初始化为正无穷，以便记录最小值
X1, Y1 = float('inf'), float('inf')
# 右上角顶点，初始化为负无穷，以便记录最大值
X2, Y2 = -float('inf'), -float('inf')

for x1, y1, x2, y2 in rectangles:
    # 取小矩形左下角顶点的最小值
    X1, Y1 = min(X1, x1), min(Y1, y1)
    # 取小矩形右上角顶点的最大值
    X2, Y2 = max(X2, x2), max(Y2, y2)

// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 计算小矩形区域的边界坐标，返回四个最可能成为边界的坐标值
func bounds(rects [][]int) (float64, float64, float64, float64) {
    x1, y1, x2, y2 := math.Inf(1), math.Inf(1), math.Inf(-1), math.Inf(-1)
    for _, rect := range rects {
        x1, y1 = math.Min(float64(x1), float64(rect[0])), math.Min(float64(y1), float64(rect[1]))
        x2, y2 = math.Max(float64(x2), float64(rect[2])), math.Max(float64(y2), float64(rect[3]))
    }
    return x1, y1, x2, y2
}

// 计算覆盖所有小矩形的最小大矩形
func minRectangle(rects [][]int) int {
    x1, y1, x2, y2 := bounds(rects)
    return int(math.Ceil((x2-x1)*(y2-y1)))
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 初始化为正无穷，以便记录最小值
var X1 = Infinity, Y1 = Infinity;
// 初始化为负无穷，以便记录最大值
var X2 = -Infinity, Y2 = -Infinity;

// 遍历所有矩形
for (var i = 0; i < rectangles.length; i++) {
    // 取出当前矩形的左下角和右上角坐标
    var x1 = rectangles[i][0];
    var y1 = rectangles[i][1];
    var x2 = rectangles[i][2];
    var y2 = rectangles[i][3];
    // 取小矩形左下角顶点的最小值
    X1 = Math.min(X1, x1);
    Y1 = Math.min(Y1, y1);
    // 取小矩形右上角顶点的最大值
    X2 = Math.max(X2, x2);
    Y2 = Math.max(Y2, y2);
}

这样就能求出完美矩形的左下角顶点坐标 (X1, Y1) 和右上角顶点的坐标 (X2, Y2) 了。

计算出的 X1,Y1,X2,Y2 坐标是完美矩形的「理论坐标」，如果所有小矩形的面积之和不等于这个完美矩形的理论面积，那么说明最终形成的图形肯定存在空缺或者重叠，肯定不是完美矩形。

代码可以进一步：

// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

public boolean isRectangleCover(int[][] rectangles) {
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
    // 记录所有小矩形的面积之和
    int actual_area = 0;
    for (int[] rectangle : rectangles) {
        int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
        // 计算完美矩形的理论坐标
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // 累加所有小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1);
    }

    // 计算完美矩形的理论面积
    int expected_area = (X2 - X1) * (Y2 - Y1);
    // 面积应该相同
    return actual_area == expected_area;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 判断是否为完美矩形
bool isRectangleCover(vector<vector<int>>& rectangles) {
    // 初始化完美矩形的理论坐标，X1, Y1 分别为正无穷，X2, Y2 分别为负无穷
    int X1 = INT_MAX, Y1 = INT_MAX;
    int X2 = INT_MIN, Y2 = INT_MIN;
    int actual_area = 0; // 记录所有小矩形的面积之和

    // 遍历所有小矩形
    for (auto& rectangle : rectangles) {
        int x1 = rectangle[0], y1 = rectangle[1];
        int x2 = rectangle[2], y2 = rectangle[3];

        // 计算完美矩形的理论坐标
        X1 = min(X1, x1);
        Y1 = min(Y1, y1);
        X2 = max(X2, x2);
        Y2 = max(Y2, y2);

        // 累加所有小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1);
    }

    // 计算完美矩形的理论面积
    int expected_area = (X2 - X1) * (Y2 - Y1);
    // 面积应该相同
    if (actual_area != expected_area) {
        return false; // 如果面积不相同，返回 false
    }

    return true; // 否则返回 true
}

def isRectangleCover(rectangles: List[List[int]]) -> bool:
    X1, Y1 = float('inf'), float('inf')
    X2, Y2 = -float('inf'), -float('inf')
    # 记录所有小矩形的面积之和
    actual_area = 0
    for x1, y1, x2, y2 in rectangles:
        # 计算完美矩形的理论坐标
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)
        # 累加所有小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1)

    # 计算完美矩形的理论面积
    expected_area = (X2 - X1) * (Y2 - Y1)
    # 面积应该相同
    if actual_area != expected_area:
        return False

    return True

// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

func isRectangleCover(rectangles [][]int) bool {
    // 初始化完美矩形的理论坐标
    X1, Y1 := math.MaxInt64, math.MaxInt64
    X2, Y2 := math.MinInt64, math.MinInt64
    // 记录所有小矩形的面积之和
    actualArea := 0

    for _, rectangle := range rectangles {
        x1, y1, x2, y2 := rectangle[0], rectangle[1], rectangle[2], rectangle[3]
        // 计算完美矩形的理论坐标
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)
        // 累加所有小矩形的面积
        actualArea += (x2 - x1) * (y2 - y1)
    }

    // 计算完美矩形的理论面积
    expectedArea := (X2 - X1) * (Y2 - Y1)
    // 面积应该相同
    if actualArea != expectedArea {
        return false
    }

    return true
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

/**
 * @param {number[][]} rectangles
 * @return {boolean}
 */
function isRectangleCover(rectangles) {
    var X1 = Infinity, 
        Y1 = Infinity;
    var X2 = -Infinity, 
        Y2 = -Infinity;
    var actual_area = 0;
    // 遍历所有矩形并记录必要信息
    for (var i = 0; i < rectangles.length; i++) {
        var rect = rectangles[i];
        var x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        // 计算完美矩形的理论坐标
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // 累加所有小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1);
    }
    // 计算完美矩形的理论面积
    var expected_area = (X2 - X1) * (Y2 - Y1);
    // 面积应该相同
    if(actual_area != expected_area){
        return false;
    }
    return true;
}

这样，「面积」这个维度就完成了，思路其实不难，无非就是假设最终形成的图形是个完美矩形，然后比较面积是否相等，如果不相等的话说明最终形成的图形一定存在空缺或者重叠部分，不是完美矩形。

但是反过来说，如果面积相同，是否可以证明最终形成的图形是完美矩形，一定不存在空缺或者重叠？

肯定是不行的，举个很简单的例子，你假想一个完美矩形，然后我在它中间挖掉一个小矩形，把这个小矩形向下平移一个单位。这样小矩形的面积之和没变，但是原来的完美矩形中就空缺了一部分，也重叠了一部分，已经不是完美矩形了。

综上，即便面积相同，并不能完全保证不存在空缺或者重叠，所以我们需要从「顶点」的维度来辅助判断。

记得小学的时候有一道智力题，给你一个矩形，切一刀，剩下的图形有几个顶点？答案是，如果沿着对角线切，就剩 3 个顶点；如果横着或者竖着切，剩 4 个顶点；如果只切掉一个小角，那么会出现 5 个顶点。

回到这道题，我们接下来的分析也有那么一点智力题的味道。

显然，完美矩形一定只有四个顶点。矩形嘛，按理说应该有四个顶点，如果存在空缺或者重叠的话，肯定不是四个顶点，比如说题目的这两个例子就有不止 4 个顶点：

Note

我也不知道应该用「顶点」还是「角」来形容，好像都不太准确，本文统一用「顶点」来形容，大家理解就好~

只要我们想办法计算 rectangles 中的小矩形最终形成的图形有几个顶点，就能判断最终的图形是不是一个完美矩形了。

那么顶点是如何形成的呢？我们倒是一眼就可以看出来顶点在哪里，问题是如何让计算机，让算法知道某一个点是不是顶点呢？这也是本题的难点所在。

看下图的四种情况：

图中画红点的地方，什么时候是顶点，什么时候不是顶点？显然，情况一和情况三的时候是顶点，而情况二和情况四的时候不是顶点。

也就是说，当某一个点同时是 2 个或者 4 个小矩形的顶点时，该点最终不是顶点；当某一个点同时是 1 个或者 3 个小矩形的顶点时，该点最终是一个顶点。

注意，2 和 4 都是偶数，1 和 3 都是奇数，我们想计算最终形成的图形中有几个顶点，也就是要筛选出那些出现了奇数次的顶点，可以这样写代码：

// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

/**
 * 计算小矩形是否能拼成完美矩形
 * @param rectangles 小矩形
 * @return boolean
 */
public boolean isRectangleCover(int[][] rectangles) {
    // 定义完美矩形的左下角和右上角的坐标
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
    // 定义小矩形的面积之和
    int actual_area = 0;
    // 定义哈希集合，记录最终图形的顶点坐标
    Set<String> points = new HashSet<>();
    for (int[] rectangle: rectangles) {
        int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
        // 更新完美矩形的左下角和右上角的坐标
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);

        // 计算小矩形的面积并加入到面积之和中
        actual_area += (x2 - x1) * (y2 - y1);
        // 计算小矩形的每个点的坐标
        String p1 = x1 + "," + y1, // 左下角坐标
               p2 = x1 + "," + y2, // 左上角坐标
               p3 = x2 + "," + y1, // 右下角坐标
               p4 = x2 + "," + y2; // 右上角坐标
        // 遍历小矩形的每个点，如果存在在集合中，就删除；
        // 如果不存在在集合中，就添加；
        // 在集合中剩下的点都是出现奇数次的点
        for (String p: Arrays.asList(p1, p2, p3, p4)) {
            if (points.contains(p)) points.remove(p);
            else points.add(p);
        }
    }

    // 计算理论上完美矩形的面积
    int expected_area = (X2 - X1) * (Y2 - Y1);
    if (actual_area != expected_area) return false; // 如果小矩形面积之和不等于完美矩形的面积，则不能拼成完美矩形
    // 如果顶点数量不为4或者顶点中不包含完美矩形的四个角，则不能拼成完美矩形
    if (points.size() != 4 || !points.contains(X1 + "," + Y1) || !points.contains(X1 + "," + Y2) || !points.contains(X2 + "," + Y1) || !points.contains(X2 + "," + Y2)) return false;

    return true;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 给定一个矩形列表，判断这些矩形是否合法（不重叠，且其总面积恰好等于他们覆盖的面积和），并返回结果。
bool isRectangleCover(vector<vector<int>>& rectangles) {
    int X1 = INT_MAX, Y1 = INT_MAX;
    int X2 = INT_MIN, Y2 = INT_MIN;

    int actual_area = 0;
    set<pair<int, int>> points;
    for(auto& rec : rectangles) {
        int x1 = rec[0], y1 = rec[1], x2 = rec[2], y2 = rec[3];
        // 记录这些矩形中确定的大矩形四个角的坐标
        X1 = min(X1, x1); Y1 = min(Y1, y1);
        X2 = max(X2, x2); Y2 = max(Y2, y2);

        // 计算这些矩形的面积和，并同时记录所有矩形小矩形子对象的四个顶点，以及确保小矩形顶点恰好被覆盖一次
        actual_area += (x2 - x1) * (y2 - y1);
        // 重组原小矩形的四个顶点的坐标
        auto p1 = make_pair(x1, y1), p2 = make_pair(x1, y2);
        auto p3 = make_pair(x2, y1), p4 = make_pair(x2, y2);
        // 对于每个点，如果存在集合中，删除它；
        // 如果不存在集合中，添加它；
        // 在集合中剩下的点都是出现奇数次的点
        for(auto p : {p1, p2, p3, p4}) {
            if(points.count(p)) points.erase(p);
            else points.insert(p);
        }
    }

    // 计算最终连续的大矩形的面积
    int expected_area = (X2 - X1) * (Y2 - Y1);
    if(actual_area != expected_area) {
        return false;
    }

    // 线面积为矩形的面积，四个顶点都必须存在且仅被计算出现奇数次
    return points.size() == 4 &&
        points.count(make_pair(X1, Y1)) &&
        points.count(make_pair(X1, Y2)) &&
        points.count(make_pair(X2, Y1)) &&
        points.count(make_pair(X2, Y2));
}

def isRectangleCover(rectangles: List[List[int]]) -> bool:
    X1, Y1 = float('inf'), float('inf')
    X2, Y2 = -float('inf'), -float('inf')

    actual_area = 0
    # 哈希集合，记录最终图形的顶点
    points = set()
    for x1, y1, x2, y2 in rectangles:
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)

        actual_area += (x2 - x1) * (y2 - y1)
        # 先算出小矩形每个点的坐标
        p1, p2 = (x1, y1), (x1, y2)
        p3, p4 = (x2, y1), (x2, y2)
        # 对于每个点，如果存在集合中，删除它；
        # 如果不存在集合中，添加它；
        # 在集合中剩下的点都是出现奇数次的点
        for p in [p1, p2, p3, p4]:
            if p in points: points.remove(p)
            else: points.add(p)

    expected_area = (X2 - X1) * (Y2 - Y1)
    if actual_area != expected_area:
        return False

    return True

// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

func isRectangleCover(rectangles [][]int) bool {
    X1, Y1 := math.MaxInt64, math.MaxInt64
    X2, Y2 := math.MinInt64, math.MinInt64

    actualArea := 0
    // 哈希集合，记录最终图形的顶点
    points := make(map[[2]int]bool)
    for _, rectangle := range rectangles {
        x1, y1, x2, y2 := rectangle[0], rectangle[1], rectangle[2], rectangle[3]
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)

        actualArea += (x2 - x1) * (y2 - y1)
        // 先算出小矩形每个点的坐标
        p1, p2 := [2]int{x1, y1}, [2]int{x1, y2}
        p3, p4 := [2]int{x2, y1}, [2]int{x2, y2}
        // 对于每个点，如果存在集合中，删除它；
        // 如果不存在集合中，添加它；
        // 在集合中剩下的点都是出现奇数次的点
        for _, p := range []([2]int){p1, p2, p3, p4} {
            if _, ok := points[p]; ok {
                delete(points, p)
            } else {
                points[p] = true
            }
        }
    }

    expectedArea := (X2 - X1) * (Y2 - Y1)
    if actualArea != expectedArea {
        return false
    }

    return len(points) == 4 &&
        points[[2]int{X1, Y1}] &&
        points[[2]int{X1, Y2}] &&
        points[[2]int{X2, Y1}] &&
        points[[2]int{X2, Y2}]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

// 使用 var 关键字声明函数
var isRectangleCover = function(rectangles) {
  // 初始化顶点边界，由于是矩形，X1 和 Y1 取最大值，X2 和 Y2 取最小值，这样才是最终的矩形边界
  let X1 = Infinity, Y1 = Infinity;
  let X2 = -Infinity, Y2 = -Infinity;

  // 实际面积，遍历每个矩形时累加每个矩形的面积
  let actual_area = 0;

  // 哈希集合，记录最终图形的所有点坐标
  const points = new Set();

  for (const [x1, y1, x2, y2] of rectangles) {
    // 更新顶点边界
    X1 = Math.min(X1, x1);
    Y1 = Math.min(Y1, y1);
    X2 = Math.max(X2, x2);
    Y2 = Math.max(Y2, y2);

    // 累加实际面积
    actual_area += (x2 - x1) * (y2 - y1);

    // 将矩形每个顶点坐标通过数组存储
    const p1 = [x1, y1], p2 = [x1, y2], p3 = [x2, y1], p4 = [x2, y2];

    // 对每个顶点进行判断，如果是已确认的点，则剔除；否则加入
    for (const p of [p1, p2, p3, p4]) {
      if (points.has(p)) {
        points.delete(p);
      } else {
        points.add(p);
      }
    }
  }

  // 期望面积，即边界宽度和高度的乘积
  const expected_area = (X2 - X1) * (Y2 - Y1);

  // 如果实际面积与期望面积不等，则不符合条件
  if (actual_area !== expected_area) return false;

  return true;
};

这段代码中，我们用一个 points 集合记录 rectangles 中小矩形组成的最终图形的顶点坐标，关键逻辑在于如何向 points 中添加坐标：

如果某一个顶点 p 存在于集合 points 中，则将它删除；如果不存在于集合 points 中，则将它插入。

这个简单的逻辑，让 points 集合最终只会留下那些出现了 1 次或者 3 次的顶点，那些出现了 2 次或者 4 次的顶点都被消掉了。

那么首先想到，points 集合中最后应该只有 4 个顶点对吧，如果 len(points) != 4 说明最终构成的图形肯定不是完美矩形。

但是如果 len(points) == 4 是否能说明最终构成的图形肯定是完美矩形呢？也不行，因为题目并没有说 rectangles 中的小矩形不存在重复，比如下面这种情况：

下面两个矩形重复了，按照我们的算法逻辑，它们的顶点都被消掉了，最终是剩下了四个顶点；再看面积，完美矩形的理论坐标是图中红色的点，计算出的理论面积和实际面积也相同。但是显然这种情况不是题目要求完美矩形。

所以不仅要保证 len(points) == 4，而且要保证 points 中最终剩下的点坐标就是完美矩形的四个理论坐标，直接看代码吧：

// 注意：java 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

public boolean isRectangleCover(int[][] rectangles) {
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
    
    HashSet<String> points = new HashSet<>();
    int actual_area = 0;
    for (int[] rectangle : rectangles) {
        // 计算完美矩形的理论顶点坐标
        X1 = Math.min(X1, rectangle[0]);
        Y1 = Math.min(Y1, rectangle[1]);
        X2 = Math.max(X2, rectangle[2]);
        Y2 = Math.max(Y2, rectangle[3]);
        // 累加小矩形的面积
        actual_area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
        // 记录最终形成的图形中的顶点
        String p1 = rectangle[0] + "," + rectangle[1];
        String p2 = rectangle[0] + "," + rectangle[3];
        String p3 = rectangle[2] + "," + rectangle[1];
        String p4 = rectangle[2] + "," + rectangle[3];
        for (String p : new String[]{p1, p2, p3, p4}) {
            if (points.contains(p)) {
                points.remove(p);
            } else {
                points.add(p);
            }
        }
    }
    // 判断面积是否相同
    int expected_area = (X2 - X1) * (Y2 - Y1);
    if (actual_area != expected_area) {
        return false;
    }
    // 判断最终留下的顶点个数是否为 4
    if (points.size() != 4) {
        return false;
    }
    // 判断留下的 4 个顶点是否是完美矩形的顶点
    String[] ps = new String[]{X1 + "," + Y1, X1 + "," + Y2, X2 + "," + Y1, X2 + "," + Y2};
    for (String p : ps) {
        if (!points.contains(p)) {
            return false;
        }
    }
    // 面积和顶点都对应，说明矩形符合题意
    return true;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

bool isRectangleCover(vector<vector<int>>& rectangles) {
    int X1 = INT_MAX, Y1 = INT_MAX;
    int X2 = INT_MIN, Y2 = INT_MIN;
    
    set<pair<int, int>> points;
    int actual_area = 0;
    for (auto& r : rectangles) {
        int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3];
        // 计算完美矩形的理论顶点坐标
        X1 = min(X1, x1);
        Y1 = min(Y1, y1);
        X2 = max(X2, x2);
        Y2 = max(Y2, y2);
        // 累加小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1);
        // 记录最终形成的图形中的顶点
        pair<int, int> p1(x1, y1), p2(x1, y2);
        pair<int, int> p3(x2, y1), p4(x2, y2);
        for (auto p : {p1, p2, p3, p4}) {
            if (points.count(p)) {
                points.erase(p);
            } else {
                points.insert(p);
            }
        }
    }
    // 判断面积是否相同
    int expected_area = (X2 - X1) * (Y2 - Y1);
    if (actual_area != expected_area) {
        return false;
    }
    // 判断最终留下的顶点个数是否为 4
    if (points.size() != 4) {
        return false;
    }
    // 判断留下的 4 个顶点是否是完美矩形的顶点
    if (!points.count(make_pair(X1, Y1))) {
        return false;
    }
    if (!points.count(make_pair(X1, Y2))) {
        return false;
    }
    if (!points.count(make_pair(X2, Y1))) {
        return false;
    }
    if (!points.count(make_pair(X2, Y2))) {
        return false;
    }
    // 面积和顶点都对应，说明矩形符合题意
    return true;
}

def isRectangleCover(rectangles: List[List[int]]) -> bool:
    X1, Y1 = float('inf'), float('inf')
    X2, Y2 = -float('inf'), -float('inf')
    
    points = set()
    actual_area = 0
    for x1, y1, x2, y2 in rectangles:
        # 计算完美矩形的理论顶点坐标
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)
        # 累加小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1)
        # 记录最终形成的图形中的顶点
        p1, p2 = (x1, y1), (x1, y2)
        p3, p4 = (x2, y1), (x2, y2)
        for p in [p1, p2, p3, p4]:
            if p in points: points.remove(p)
            else:           points.add(p)
    # 判断面积是否相同
    expected_area = (X2 - X1) * (Y2 - Y1)
    if actual_area != expected_area:
        return False
    # 判断最终留下的顶点个数是否为 4
    if len(points) != 4:       return False
    # 判断留下的 4 个顶点是否是完美矩形的顶点
    if (X1, Y1) not in points: return False
    if (X1, Y2) not in points: return False
    if (X2, Y1) not in points: return False
    if (X2, Y2) not in points: return False
    # 面积和顶点都对应，说明矩形符合题意
    return True

// 注意：go 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

func isRectangleCover(rectangles [][]int) bool {
    var (
        X1, Y1 int = math.MaxInt32, math.MaxInt32
        X2, Y2 int = -math.MaxInt32, -math.MaxInt32
        points  = make(map[[2]int]bool)
        actualArea int
    )
    
    for _, rect := range rectangles {
        x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
        // 统计最大完美矩形的理论顶点坐标
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)
        // 累加每个小矩形的面积，并记录最终形成的图形中的顶点
        actualArea += (x2 - x1) * (y2 - y1)
        p1, p2 := [2]int{x1, y1}, [2]int{x1, y2}
        p3, p4 := [2]int{x2, y1}, [2]int{x2, y2}
        for _, p := range [...] [2]int{p1, p2, p3, p4} {
            if _, ok := points[p]; ok {
                delete(points, p)
            } else {
                points[p] = true
            }
        }
    }
    // 判断面积是否相同
    expectedArea := (X2 - X1) * (Y2 - Y1)
    if actualArea != expectedArea {
        return false
    }
    // 判断最终留下的顶点个数是否为 4
    if len(points) != 4 {
        return false
    }
    // 判断留下的 4 个顶点是否是完美矩形的顶点
    // 使用 delete() 和 map 类型，可以方便进行 lookup 操作
    // 而 [] 是无法直接进行 lookup 操作的
    if _, ok := points[[2]int{X1, Y1}]; !ok {
        return false
    }
    if _, ok := points[[2]int{X1, Y2}]; !ok {
        return false
    }
    if _, ok := points[[2]int{X2, Y1}]; !ok {
        return false
    }
    if _, ok := points[[2]int{X2, Y2}]; !ok {
        return false
    }
    // 面积和顶点都对应，说明矩形符合题意
    return true
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 python 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 python 代码对比查看。

function isRectangleCover(rectangles) {
    let X1 = Infinity, Y1 = Infinity;
    let X2 = -Infinity, Y2 = -Infinity;
    
    const points = new Set();
    let actual_area = 0;
    for (let i = 0; i < rectangles.length; i++) {
        const [x1, y1, x2, y2] = rectangles[i];
        // 计算完美矩形的理论顶点坐标
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // 累加小矩形的面积
        actual_area += (x2 - x1) * (y2 - y1);
        // 记录最终形成的图形中的顶点
        const p1 = [x1, y1], p2 = [x1, y2];
        const p3 = [x2, y1], p4 = [x2, y2];
        for (const p of [p1, p2, p3, p4]) {
            if (points.has(p)) { points.delete(p); }
            else { points.add(p); }
        }
    }
    // 判断面积是否相同
    const expected_area = (X2 - X1) * (Y2 - Y1);
    if (actual_area !== expected_area) { return false; }
    // 判断最终留下的顶点个数是否为 4
    if (points.size !== 4) { return false; }
    // 判断留下的 4 个顶点是否是完美矩形的顶点
    if (!points.has([X1, Y1])) { return false; }
    if (!points.has([X1, Y2])) { return false; }
    if (!points.has([X2, Y1])) { return false; }
    if (!points.has([X2, Y2])) { return false; }
    // 面积和顶点都对应，说明矩形符合题意
    return true;
}

这就是最终的解法代码，从「面积」和「顶点」两个维度来判断：

1、判断面积，通过完美矩形的理论坐标计算出一个理论面积，然后和 rectangles 中小矩形的实际面积和做对比。

2、判断顶点，points 集合中应该只剩下 4 个顶点且剩下的顶点必须都是完美矩形的理论顶点。

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：