矩形面积 II

标签: 线段树 数组 有序集合 扫描线

难度: Hard

给你一个轴对齐的二维数组 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。

计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。

返回 总面积 。因为答案可能太大，返回 109 + 7 的 模 。

示例 1：

输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
解释：如图所示，三个矩形覆盖了总面积为 6 的区域。
从(1,1)到(2,2)，绿色矩形和红色矩形重叠。
从(1,0)到(2,3)，三个矩形都重叠。

示例 2：

输入：rectangles = [[0,0,1000000000,1000000000]]
输出：49
解释：答案是 1018 对 (109 + 7) 取模的结果， 即 49 。

提示：

  • 1 <= rectangles.length <= 200
  • rectanges[i].length = 4
  • 0 <= xi1, yi1, xi2, yi2 <= 109

Submission

运行时间: 36 ms

内存: 16.3 MB

class Solution:
    def rectangleArea(self, a: List[List[int]]) -> int:
        x = []
        for rec in a:
            x += [rec[0], rec[2]]
        
        s = sorted(list(set(x)))
        p = {x: i for i, x in enumerate(s)}

        n = len(s)
        cnt = [[] for _ in range(n)]

        for x1, y1, x2, y2 in a:
            for i in range(p[x1], p[x2]):
                cnt[i].append((y1, y2))
        
        Y = []
        for i in range(n):
            Y.append(0)
            if not cnt[i]:
                continue

            cnt[i].sort(key = lambda x: x[0])
            sm = 0
            st, top = cnt[i][0]
            for y1, y2 in cnt[i]:
                if y1 > top:
                    Y[-1] += top - st
                    st, top = y1, y2
                else:
                    top = max(top, y2)
            Y[-1] += top - st
    
        ans = 0
        for i in range(1, n):
            ans += (s[i] - s[i - 1]) * Y[i - 1]
    
        return ans % (10 ** 9 + 7)

Explain

该题解的思路是利用扫描线算法。首先将所有矩形的左右边界x坐标去重并排序，建立x坐标到索引的映射。然后遍历每个矩形，将其在x方向上覆盖的区间内的每个位置记录下该矩形在y方向上的区间。接着对于x方向每个分割后的小区间，将其包含的y区间按起点排序，然后用类似合并区间的方法计算出y方向覆盖的长度。最后将所有小矩形区域的面积累加起来即可得到最终结果。

时间复杂度: O(n^2logn)

空间复杂度: O(n^2)

class Solution:
    def rectangleArea(self, a: List[List[int]]) -> int:
        # 获取所有x坐标并去重排序
        x = []
        for rec in a:
            x += [rec[0], rec[2]]
        
        s = sorted(list(set(x)))
        # 建立x坐标到索引的映射
        p = {x: i for i, x in enumerate(s)}

        n = len(s)
        # 记录每个x区间对应的y区间
        cnt = [[] for _ in range(n)]

        for x1, y1, x2, y2 in a:
            for i in range(p[x1], p[x2]):
                cnt[i].append((y1, y2))
        
        Y = []
        for i in range(n):
            Y.append(0)
            if not cnt[i]:
                continue

            # 对y区间按起点排序
            cnt[i].sort(key = lambda x: x[0])
            sm = 0
            st, top = cnt[i][0]
            # 合并y区间并累加覆盖长度
            for y1, y2 in cnt[i]:
                if y1 > top:
                    Y[-1] += top - st
                    st, top = y1, y2
                else:
                    top = max(top, y2)
            Y[-1] += top - st
    
        # 计算最终覆盖的总面积
        ans = 0
        for i in range(1, n):
            ans += (s[i] - s[i - 1]) * Y[i - 1]
    
        return ans % (10 ** 9 + 7)

Explore

在扫描线算法中，处理重叠的矩形的关键在于合并重叠的y区间。算法首先将每个x区间内的所有y区间收集起来，然后按照y区间的起点进行排序。通过遍历排序后的y区间列表，若当前区间与前一个区间重叠（即当前区间的起点小于或等于前一个区间的终点），则将这两个区间合并为一个新区间，其终点为两个区间终点的最大值。这样，每个x区间内的y区间都被合并为几个不重叠的区间，确保每个具体的y区间只计算一次面积。

去重和排序x坐标是为了确定x方向上的区间划分。首先，去重是必要的，因为重复的x坐标对于划分区间没有帮助，只会增加不必要的计算量。其次，排序后的x坐标可以帮助我们确定每一个小的x区间（即两个相邻的x坐标之间的区间），这些区间是计算面积分割的基础。在已排序的x坐标基础上，我们可以确保遍历这些x区间时，是按照从左到右的顺序处理，从而正确地计算覆盖在每个x区间上的y区间的面积。

`cnt`数组是用来存储每个x区间对应的所有y区间的集合。在遍历输入的矩形时，算法会将每个矩形的y区间根据其x边界映射到对应的`cnt`数组的元素中。这样，`cnt[i]`包含了所有在第i个x区间（由相邻的x坐标定义）内的y区间。这个数组的存在使得算法可以对单个x区间内的所有y区间进行处理，如合并重叠区间，并计算该x区间的总y覆盖长度，这是计算总面积的关键步骤。

对y区间按起点进行排序是为了简化合并重叠区间的过程。排序后的y区间列表允许算法逐一检查每个区间，并与前一个合并后的区间进行比较，判断是否需要合并。如果列表不经排序，算法在处理每个新的y区间时，可能需要回溯到之前的区间进行比较，这会复杂化合并过程并增加算法的时间复杂度。排序确保了处理的顺序性和简洁性，使得合并重叠区间的操作更高效、直观。