0850：矩形面积 II（2235 分）

2018-06-10 约 1026 字预计阅读 3 分钟次阅读

力扣第 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，上一轮区间集合覆盖的长度 w，即可计算出 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


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((-1,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 add,y1,y2 in d[x]:
                ct[(y1,y2)] += add
                if not ct[(y1,y2)]:
                    del ct[(y1,y2)]
            pre = x
        return res

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

#2

还可以用线段树维护区间覆盖的长度 w
直接维护覆盖的长度不好处理，一种方法是维护"区间的最小值" t 和 t 对应的长度 sz
- 那么假如总区间的最小值 t>0，说明整个区间都被覆盖
- 否则 t=0，那么覆盖的长度为总区间长度 s - (t 对应的 sz)

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        def build(o,l,r):
            if l==r:
                sz[o] = H[r+1]-H[r]
                return
            m = (l+r)//2
            build(o*2,l,m)
            build(o*2+1,m+1,r)
            sz[o] = sz[o*2]+sz[o*2+1]

        def do(o,x):           
            t[o] += x
            f[o] += x

        def down(o):
            if f[o]:
                do(o*2,f[o])
                do(o*2+1,f[o])
                f[o] = 0

        def update(a,b,x,o,l,r):
            if a<=l and r<=b:
                do(o,x)
                return 
            m = (l+r)//2
            down(o)
            if a<=m: update(a,b,x,o*2,l,m)
            if m<b: update(a,b,x,o*2+1,m+1,r)
            t[o] = min(t[o*2],t[o*2+1])
            sz[o] = sz[o*2]*(t[o]==t[o*2])+sz[o*2+1]*(t[o]==t[o*2+1])

        H = sorted({y for x1,y1,x2,y2 in rectangles for y in [y1,y2]})
        N = len(H)-1
        t,f,sz = [0]*N*4,[0]*N*4,[0]*N*4
        build(1,0,N-1)
        d = defaultdict(list)
        for x1,y1,x2,y2 in rectangles:
            d[x1].append((1,y1,y2))
            d[x2].append((-1,y1,y2))
        res,pre = 0,0
        mod = 10**9+7
        s = H[-1]-H[0]
        for x in sorted(d):
            w = s-(sz[1] if t[1]==0 else 0)
            res += (x-pre)*w
            res %= mod
            for add,y1,y2 in d[x]:
                i = bisect_left(H,y1)
                j = bisect_left(H,y2)
                update(i,j-1,add,1,0,N-1)
            pre = x
        return res

19 ms

#3

还有种特殊的写法
本题的线段树有两个特殊性
- 只查询根节点
- 只删除之前添加过的区间
所以可以不用下传懒标记

解答

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        def build(o,l,r):
            if l==r:
                sz[o] = H[r+1]-H[r]
                return
            m = (l+r)//2
            build(o*2,l,m)
            build(o*2+1,m+1,r)
            sz[o] = sz[o*2]+sz[o*2+1]

        def up(o,l,r):            
            if f[o]>0:
                t[o] = sz[o]
            elif l==r:
                t[o] = 0
            else:
                t[o] = t[o*2]+t[o*2+1]

        def update(a,b,x,o,l,r):
            if a<=l and r<=b:
                f[o] += x
                up(o,l,r)
                return 
            m = (l+r)//2
            if a<=m: update(a,b,x,o*2,l,m)
            if m<b: update(a,b,x,o*2+1,m+1,r)
            up(o,l,r)

        H = sorted({y for x1,y1,x2,y2 in rectangles for y in [y1,y2]})
        N = len(H)-1
        t,f,sz = [0]*N*4,[0]*N*4,[0]*N*4
        build(1,0,N-1)
        d = defaultdict(list)
        for x1,y1,x2,y2 in rectangles:
            d[x1].append((1,y1,y2))
            d[x2].append((-1,y1,y2))
        res,pre = 0,0
        mod = 10**9+7
        for x in sorted(d):
            res += (x-pre)*t[1]
            res %= mod
            for add,y1,y2 in d[x]:
                i = bisect_left(H,y1)
                j = bisect_left(H,y2)
                update(i,j-1,add,1,0,N-1)
            pre = x
        return res

11 ms

目录

0850：矩形面积 II（2235 分）

题目

分析

#1

#2

#3

解答