0850：矩形面积 II（2235 分）

2018-06-10 约 522 字预计阅读 2 分钟次阅读

力扣第 88 场周赛第 4 题

题目

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

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

返回 总面积 。因为答案可能太大，返回 10⁹ + 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
解释：答案是 10¹⁸ 对 (10⁹ + 7) 取模的结果， 即 49 。

提示：

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= x_i1, y_i1, x_i2, y_i2 <= 10⁹

分析

#1

类似 0218，不过遍历坐标 x 时，要维护的不是高度集合，而是区间集合
每一轮根据当前横坐标 x 、上一轮横坐标 pre，上一轮区间集合覆盖的长度 h，即可计算出 pre 到 x 的面积

 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
26
27


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        mod = 10**9+7
        d = defaultdict(list)
        for x1,y1,x2,y2 in rectangles:
            d[x1].append((1,y1,y2))
            d[x2].append((0,y1,y2))
        def cal(ct):
            res, r = 0, -inf
            for a,b in sorted(ct):
                res += max(0,b-max(a,r))
                r = max(r,b)
            return res
        res = 0
        ct, pre = defaultdict(int),0
        for x in sorted(d):
            res += (x-pre)*cal(ct)
            res %= mod
            for flag,y1,y2 in d[x]:
                if flag:
                    ct[(y1,y2)] += 1
                else:
                    ct[(y1,y2)] -= 1
                    if not ct[(y1,y2)]:
                        del ct[(y1,y2)]
            pre = x
        return res

时间复杂度 O(N^2)，15 ms

#2

区间集合的情况可以用线段树维护

目录

0850：矩形面积 II（2235 分）

题目

分析

#1

#2

解答