对于 LeetCode 391 完美矩形问题,需要判断一组矩形是否恰好无重叠无遗漏地覆盖一个矩形区域。关键条件是:所有小矩形的总面积等于最终大矩形的面积,且只有大矩形的四个顶点出现奇数次,其余顶点均出现偶数次。

以下是 Java 实现,采用顶点奇偶性统计和面积校验:

class Solution {
public boolean isRectangleCover(int[][] rectangles) {
int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
long sumArea = 0;
Set points = new HashSet<>();

    for (int[] rect : rectangles) {
        int x = rect[0], y = rect[1], a = rect[2], b = rect[3];
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
        maxX = Math.max(maxX, a);
        maxY = Math.max(maxY, b);
        
        sumArea += (long)(a - x) * (b - y);
        
        long[] corners = {encode(x, y), encode(a, y), encode(a, b), encode(x, b)};
        for (long corner : corners) {
            if (points.contains(corner)) points.remove(corner);
            else points.add(corner);
        }
    }
    
    long totalArea = (long)(maxX - minX) * (maxY - minY);
    if (sumArea != totalArea) return false;
    if (points.size() != 4) return false;
    
    long[] expected = {encode(minX, minY), encode(minX, maxY), 
                      encode(maxX, minY), encode(maxX, maxY)};
    for (long e : expected) {
        if (!points.contains(e)) return false;
    }
    return true;
}

private long encode(int x, int y) {
    return ((long)x << 32) | (y & 0xFFFFFFFFL);
}

}

该算法遍历一次矩形数组,计算总面积和顶点奇偶性,最后校验面积和顶点,时间复杂度 O(n),空间复杂度 O(n)。

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐