1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/perfect-rectangle/description/

2.解题方法

2.1.解题思路

扫描线

2.2.解题步骤

第一步，将各个矩阵线段化。左侧边按[x,y_bottom,y_top,1]的形式存储，右侧边按[x,y_bottom,y_top,1]的形式存储，得到segments数组

第二步，将segments按x,y的顺序依次升序排列

第三步，遍历所有的线段

• 3.1.找到segments中当前x相同的一组线段，使用l和r指针进行表示

• 3.2.遍历segments[l:r]，将左侧边和右侧边分别加入或者合并到lsegs或者rsegs数组中；如果出现同侧线段相连，则合并加到对应的segs(lsegs/rsegs)数组中；如果过程中出现同侧线段覆盖，直接返回False；如果出现同侧线段被中间小矩形分开的情况，造成线段不连续，则直接将线段添加到对应segs数组中

• 3.3.根据lsegs和rsegs判断是否能形成“大矩阵”

  • 3.3.1.对于“大矩阵”最左边和最右边的线段，一定是形成一条连续的线段，所以对应lsegs和rsegs中的线段数和一定为1

  • 3.3.2.对于“大矩阵”中间的线段，lsegs和rsegs中的线段一定完全相同，进行比较返回

3.解题代码

python代码

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        # 思路：扫描线
        if not rectangles:
            return False
        # 第一步，将各个矩阵线段化。左侧边按[x,y_bottom,y_top,1]的形式存储，右侧边按[x,y_bottom,y_top,1]的形式存储，得到segments数组
        segments = []
        for x1, y1, x2, y2 in rectangles:
            segments.append([x1, y1, y2, 1])
            segments.append([x2, y1, y2, 0])
        # 第二步，将segments按x,y的顺序依次升序排列
        segments.sort()
        # 第三步，遍历所有的线段
        n = len(segments)
        l = 0
        while l < n:
            x, y1, y2, flag = segments[l]
            # 3.1.找到segments中当前x相同的一组线段，使用l和r指针进行表示
            r = l
            while r < n and segments[r][0] == x:
                r += 1
            # 3.2.遍历segments[l:r]，将左侧边和右侧边分别加入或者合并到lsegs或者rsegs数组中；如果出现同侧线段相连，则合并加到对应的segs(lsegs/rsegs)数组中；如果过程中出现同侧线段覆盖，直接返回False；如果出现同侧线段被中间小矩形分开的情况，造成线段不连续，则直接将线段添加到对应segs数组中
            lsegs, rsegs = [], []
            for i in range(l, r):
                thisx, thisy1, thisy2, thisFlag = segments[i]
                curSegs = lsegs if thisFlag else rsegs
                if not curSegs:
                    curSegs.append([thisy1, thisy2])
                else:
                    if curSegs[-1][1] == thisy1:
                        # 连续合并的情况
                        curSegs[-1][1] = thisy2
                    elif curSegs[-1][1] > thisy1:
                        # 覆盖的情况，直接返回False
                        return False
                    else:
                        # 被中间小矩形分隔开的线段，不连续
                        curSegs.append([thisy1, thisy2])
                        # print(segments[i])
            # 3.3.根据lsegs和rsegs判断是否能形成“大矩阵”
            if l == 0 or r == len(segments):
                # 3.3.1.对于“大矩阵”最左边和最右边的线段，一定是形成一条连续的线段，所以对应lsegs和rsegs中的线段数和一定为1
                if len(lsegs) + len(rsegs) != 1:
                    return False
            else:
                # 3.3.2.对于“大矩阵”中间的线段，lsegs和rsegs中的线段一定完全相同，进行比较返回
                if len(lsegs) != len(rsegs):
                    return False
                for j in range(len(lsegs)):
                    if lsegs[j][0] != rsegs[j][0] or lsegs[j][1] != rsegs[j][1]:
                        return False
            l = r
        return True

4.执行结果