0391：完美矩形（★★）

2016-01-26 约 561 字预计阅读 2 分钟次阅读

力扣第 391 题

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= rectangles.length <= 2 * 10⁴
rectangles[i].length == 4
-10⁵ <= x_i, y_i, a_i, b_i <= 10⁵

分析

精确覆盖即代表没有重叠、没有间隙，可以用扫描线算法
遍历边缘坐标 x，维护矩形的高度区间集合，如果该集合精确覆盖一个区间且一直不变，即说明是完美矩形
除了开头和结尾，只需要判断新增的和弹出的高度区间集合是否等价即可
合并区间类似 0056

 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


class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        def merge(A):
            res=[]
            for s,e in sorted(A):
                if not res or res[-1][1]<s:
                    res.append([s,e])
                elif res[-1][1]==s:
                    res[-1][1] = e
                else:
                    return 0
            return res
        d = defaultdict(lambda:defaultdict(list))
        for x,y,a,b in rectangles:
            d[x][0].append((y,b))
            d[a][1].append((y,b))
        for i,x in enumerate(sorted(d)):
            A,B = merge(d[x][0]),merge(d[x][1])
            if A==0 or B==0:
                return False
            if i==0 and len(A)!=1:
                return False
            if 0<i<len(d)-1 and A!=B:
                return False
        return True

90 ms

#2

还可以用二维差分，最后不为 0 的只有 4 个点，且应该是两个 1，两个 -1。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        d = defaultdict(int)
        for x,y,a,b in rectangles:
            d[(x,y)] += 1
            d[(x,b)] -= 1
            d[(a,y)] -= 1
            d[(a,b)] += 1
        A = [v for v in d.values() if v!=0]
        return len(A)==4 and sorted(A)==[-1,-1,1,1]

88 ms

目录

0391：完美矩形（★★）

题目

分析

#2

解答