跳至主要內容

如何判定完美矩形

labuladong原创数学数组设计约 4928 字

391. 完美矩形 https://leetcode.cn/problems/perfect-rectangle

391. Perfect Rectangle https://leetcode.com/problems/perfect-rectangle

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

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

LeetCodeDifficulty
391. Perfect Rectangle🔴

Today, we'll discuss a very interesting and somewhat challenging problem.

We know that a rectangle has four vertices, but only two vertices are needed to determine a rectangle (for example, the coordinates of the bottom-left and top-right vertices).

Let's take a look at LeetCode problem #391, "Perfect Rectangle." The problem provides an input array rectangles, which contains several quadruples (x1, y1, x2, y2). Each quadruple represents the coordinates of the bottom-left and top-right vertices of a rectangle.

In other words, the input rectangles array consists of many small rectangles. The task is to output a boolean value indicating whether these small rectangles can form a "perfect rectangle." The function signature is as follows:

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

A "perfect rectangle" means that the small rectangles in rectangles must form a large rectangle without any overlaps or gaps.

For example, the problem provides several examples:

This problem is classified as Hard. If you haven't encountered similar problems before, it can be quite challenging.

The conventional approach would be to represent the final shape formed by the rectangles. You would also need methods to check for overlaps and gaps between rectangles, which, while possible, seems overly complex.

In reality, to determine if the final shape is a perfect rectangle, you need to consider two aspects: "area" and "vertices".

Let's start with the "area" perspective.

Each element in the rectangles array is a quadruple (x1, y1, x2, y2), representing the coordinates of the bottom-left and top-right vertices of a small rectangle.

So,假设 these small rectangles eventually form a "perfect rectangle," can you find the coordinates of the bottom-left vertex (X1, Y1) and the top-right vertex (X2, Y2) of this perfect rectangle?

This is straightforward. The bottom-left vertex (X1, Y1) is the bottom-left vertex of the smallest rectangle in rectangles that is most to the left and bottom. The top-right vertex (X2, Y2) is the top-right vertex of the smallest rectangle that is most to the right and top.

Note that we use lowercase letters for the coordinates of small rectangles and uppercase letters for the coordinates of the final perfect rectangle. The code can be written as follows:

python 🟢
# The bottom-left vertex, initialized to positive infinity to record the minimum value
X1, Y1 = inf, inf
# The top-right vertex, initialized to negative infinity to record the maximum value
X2, Y2 = -inf, -inf

for x1, y1, x2, y2 in rectangles:
    # Take the minimum value of the bottom-left vertex of the small rectangle
    X1, Y1 = min(X1, x1), min(Y1, y1)
    # Take the maximum value of the top-right vertex of the small rectangle
    X2, Y2 = max(X2, x2), max(Y2, y2)

This way, you can determine the coordinates of the bottom-left corner (X1, Y1) and the top-right corner (X2, Y2) of the perfect rectangle.

The calculated coordinates X1, Y1, X2, Y2 are the 'theoretical coordinates' of the perfect rectangle. If the sum of the areas of all small rectangles does not equal the theoretical area of this perfect rectangle, it indicates that the final shape must have gaps or overlaps, and thus it is not a perfect rectangle.

The code can be further improved:

java 🟢
boolean isRectangleCover(int[][] rectangles) {
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
    // record the sum of the areas of all small rectangles
    int actualArea = 0;
    for (int[] rect : rectangles) {
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        // calculate the theoretical coordinates of the perfect rectangle
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // accumulate the area of all small rectangles
        actualArea += (x2 - x1) * (y2 - y1);
    }

    // calculate the theoretical area of the perfect rectangle
    int expectedArea = (X2 - X1) * (Y2 - Y1);
    // the areas should be the same
    if (actualArea != expectedArea) {
        return false;
    }

    return true;
}

This way, the dimension of "area" is completed. The idea is actually not difficult. It's just about assuming that the final shape formed is a perfect rectangle and then comparing whether the areas are equal. If they are not equal, it means that the final shape must have gaps or overlaps and is not a perfect rectangle.

However, conversely, if the areas are the same, can it prove that the final shape is a perfect rectangle and definitely has no gaps or overlaps?

Certainly not. Here's a simple example: imagine a perfect rectangle, and then I cut out a small rectangle from the middle and move it down by one unit. The total area of the small rectangles hasn't changed, but the original perfect rectangle now has a gap and an overlap, and it's no longer a perfect rectangle.

In summary, even if the areas are the same, it cannot fully guarantee that there are no gaps or overlaps. Therefore, we need to use the dimension of "vertices" to help judge.

Remember a puzzle from elementary school? You're given a rectangle and asked how many vertices are left after making one cut. The answer is: if you cut along the diagonal, you're left with 3 vertices; if you cut horizontally or vertically, you have 4 vertices left; if you only cut off a small corner, you end up with 5 vertices.

Coming back to this problem, our next analysis has a bit of that puzzle flavor.

Obviously, a perfect rectangle must have only four vertices. A rectangle should ideally have four vertices. If there are gaps or overlaps, it definitely won't have four vertices. For example, the two cases in the problem have more than 4 vertices:

注

I'm not sure whether to use "vertex" or "corner" to describe it, as neither seems quite accurate. In this article, we'll use "vertex" for consistency, so just understand it in that context~

As long as we can calculate how many vertices the final shape formed by the small rectangles in rectangles has, we can determine if the final shape is a perfect rectangle.

So, how are vertices formed? We can easily see where the vertices are, but the challenge is how to make the computer, the algorithm, recognize whether a certain point is a vertex. This is the crux of the problem.

Look at the four scenarios in the following diagram:

In the places marked with red dots, when is it a vertex and when is it not? Obviously, it is a vertex in scenarios one and three, but not in scenarios two and four.

In other words, when a point is simultaneously a vertex of 2 or 4 small rectangles, it is not a vertex in the final shape; when a point is simultaneously a vertex of 1 or 3 small rectangles, it is a vertex in the final shape.

Note that 2 and 4 are even numbers, while 1 and 3 are odd numbers. To calculate how many vertices the final shape has, we need to filter out those vertices that appear an odd number of times. The code can be written as follows:

java 🟢
boolean isRectangleCover(int[][] rectangles) {
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;

    int actualArea = 0;
    // Hash set to record the vertices of the final figure
    Set<String> points = new HashSet<>();
    for (int[] rect : rectangles) {
        int 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);

        actualArea += (x2 - x1) * (y2 - y1);
        // First calculate the coordinates of each point of the small rectangle, represented by a string, for easy storage in the hash set
        String p1 = x1 + "," + y1;
        String p2 = x1 + "," + y2;
        String p3 = x2 + "," + y1;
        String p4 = x2 + "," + y2;
        // For each point, if it exists in the set, remove it;
        // if it does not exist in the set, add it;
        // The remaining points in the set are those that appear an odd number of times
        for (String p : new String[]{p1, p2, p3, p4}) {
            if (points.contains(p)) {
                points.remove(p);
            } else {
                points.add(p);
            }
        }
    }

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

    // Check the number of vertices
    if (points.size() != 4 || 
        !points.contains(X1 + "," + Y1) || 
        !points.contains(X1 + "," + Y2) || 
        !points.contains(X2 + "," + Y1) || 
        !points.contains(X2 + "," + Y2)) {
        return false;
    }

    return true;
}

In this code, we use a points set to record the vertex coordinates of the final shape formed by the small rectangles in rectangles. The key logic is how to add coordinates to the points set:

If a vertex p exists in the points set, remove it; if it does not exist, insert it.

This simple logic ensures that the points set will only retain vertices that appear 1 or 3 times, while those that appear 2 or 4 times are eliminated.

First, you might think that the points set should ultimately contain only 4 vertices, right? If len(points) != 4, it means the final shape is definitely not a perfect rectangle.

But does len(points) == 4 guarantee that the final shape is a perfect rectangle? Not necessarily, because the problem does not specify that there are no duplicate small rectangles in rectangles. For example, consider the following situation:

The two rectangles below are duplicates. According to our algorithm logic, their vertices are eliminated, leaving four vertices in the end. Looking at the area, the theoretical coordinates of the perfect rectangle are the red points in the diagram, and the calculated theoretical area matches the actual area. However, this situation is clearly not the perfect rectangle required by the problem.

So, we must ensure not only that len(points) == 4, but also that the final remaining coordinates in points are exactly the four theoretical coordinates of the perfect rectangle. Let's look at the code:

java 🟢
class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
        int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        
        Set<String> points = new HashSet<>();
        int actualArea = 0;
        for (int[] rect : rectangles) {
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            // calculate the theoretical vertex coordinates of the perfect rectangle
            X1 = Math.min(X1, x1);
            Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2);
            Y2 = Math.max(Y2, y2);
            // accumulate the area of small rectangles
            actualArea += (x2 - x1) * (y2 - y1);
            // record the vertices of the final formed shape
            String p1 = x1 + "," + y1;
            String p2 = x1 + "," + y2;
            String p3 = x2 + "," + y1;
            String p4 = x2 + "," + y2;
            for (String p : new String[]{p1, p2, p3, p4}) {
                if (points.contains(p)) {
                    points.remove(p);
                } else {
                    points.add(p);
                }
            }
        }
        // determine if the areas are the same
        int expectedArea = (X2 - X1) * (Y2 - Y1);
        if (actualArea != expectedArea) {
            return false;
        }
        // determine if the number of vertices left is 4
        if (points.size() != 4) {
            return false;
        }
        // determine if the 4 vertices left are the vertices of the perfect rectangle
        if (!points.contains(X1 + "," + Y1)) return false;
        if (!points.contains(X1 + "," + Y2)) return false;
        if (!points.contains(X2 + "," + Y1)) return false;
        if (!points.contains(X2 + "," + Y2)) return false;
        // both the area and the vertices match, indicating the rectangle meets the requirements
        return true;
    }
}

This is the final solution code, which judges from two dimensions: "area" and "vertices":

  1. Judging the Area: Calculate a theoretical area using the theoretical coordinates of a perfect rectangle, and then compare it with the sum of the actual areas of the smaller rectangles in rectangles.

  2. Judging the Vertices: The points set should contain only 4 vertices, and these remaining vertices must all be the theoretical vertices of the perfect rectangle.

上次编辑于: