力扣 391. 完美矩形

题目说明

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

提示：

  • 1 <= rectangles.length <= 2 * 10^4
  • rectangles[i].length == 4
  • -10^5 <= xi, yi, ai, bi <= 10^5

示例

示例 1:

img

1
2
3
输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。

示例 2:

img

1
2
3
输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3:

img

1
2
3
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
输出：false
解释：图形顶端留有空缺，无法覆盖成一个矩形。

示例 4:

img

1
2
3
输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，发现在判断时，完美矩形的点中，除了外圈顶点之外其他点都是成对存在，而且所有小矩形的总面积等于外圈大矩形的面积，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    /**
     * 数组
     */
    public boolean isRectangleCover(int[][] rectangles) {
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        int top = Integer.MIN_VALUE;
        int bottom = Integer.MAX_VALUE;

        int n = rectangles.length;

        HashSet<String> set = new HashSet<>();
        int sumArea = 0;

        for (int i = 0; i < n; i++) {
            int tempLeft = rectangles[i][0];
            int tempBottom = rectangles[i][1];
            int tempRight = rectangles[i][2];
            int tempTop = rectangles[i][3];

            // 标记最外圈的顶点，完美矩形的顶点总应该在最外圈
            left = Math.min(left, tempLeft);
            bottom = Math.min(bottom, tempBottom);
            right = Math.max(right, tempRight);
            top = Math.max(top, tempTop);

            // 累计每个小矩形的面积
            sumArea += (tempTop - tempBottom) * (tempRight - tempLeft);

            String lt = tempLeft + "_" + tempTop;
            String lb = tempLeft + "_" + tempBottom;
            String rt = tempRight + "_" + tempTop;
            String rb = tempRight + "_" + tempBottom;

            // 记录每个点，完美矩形除了外圈四个顶点外，其他点应该是成对出现的
            handlePoint(set, lt);
            handlePoint(set, lb);
            handlePoint(set, rt);
            handlePoint(set, rb);
        }

        // 当且仅当set集合只剩下四个顶点，而且刚好是最外圈的四个点时
        if (set.size() == 4 && 
                set.contains(left + "_" + top) && set.contains(left + "_" + bottom) &&
                set.contains(right + "_" + bottom) && set.contains(right + "_" + top)) {
            // 而且所有小矩形的面积和等于外圈大矩形的面积时
            return sumArea == (right - left) * (top - bottom);
        }

        return false;
    }

    /**
     * 操作点，保存不重复点
     */
    public void handlePoint(HashSet<String> set, String point) {
        if (!set.contains(point)) {
            set.add(point);
        }
        else {
            set.remove(point);
        }
    }
}

时间和空间效率还行，可见此解法还比较适合此题。

image-20211116091941567

总结

本题是今天的一题，难度是为困难，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。