leetcode：850. 矩形面积 II【扫描线 + 可重叠的累计长度差分数组】

分析

所谓扫描线就是按照x找到一个set，然后排一下
这样我们就可以统计在x1和x2中间的面积了，而且x1和x2中必然是横坐标填满的或者没有的，不存在中间空缺的情况
因此我们再考虑y轴上的连续性
可能会存在空缺，也就是部分连续，部分空缺
可以采用差分数组的方式
如果当目前的累计值cnt为正的话说明是有占位的，如果为0的话说明结束了，因此我们可以根据cnt的值
来锁定每个连续段的y轴长度
然后deltaY * deltaX就是这个连续段的面积

ac code

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        # X轴扫描线，Y轴差分数组
        s = set()
        for x1, y1, x2, y2 in rectangles:
            s |= {x1, x2}
        # 扫描线排序
        s = sorted(s)
        ans = 0

        for i in range(1, len(s)):
            px, x = s[i - 1], s[i]
            # 覆盖两个扫描线的区间
            # 记录垂直差分数组
            d = defaultdict(int)
            for x1, y1, x2, y2 in rectangles:
                if x1 <= px <= x <= x2:
                    d[y1] += 1
                    d[y2] -= 1
            
            cnt = 0
            for y in sorted(d):
                # 块开始
                if cnt == 0:
                    py = y
                
                cnt += d[y]

                # 块结束
                if cnt == 0:
                    ans = (ans + (x - px) * (y - py)) % MOD
            
        return ans
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

java

class Solution {

    private int MOD = (int)1e9 + 7;

    public int rectangleArea(int[][] rs) {
        // 扫描线模板题
        List<Integer> list = new ArrayList<>();
        // 记录扫描线的x轴
        for (int[] info: rs) {
            list.add(info[0]);
            list.add(info[2]);
        }
        Collections.sort(list);
        long ans = 0;
        for (int i = 1; i < list.size(); i++) {
            int a = list.get(i - 1), b = list.get(i), len = b - a;
            if (len == 0) continue;
            List<int[]> lines = new ArrayList<>();
            for (int[] info: rs) {
                // 加入覆盖区间[a,b]的矩形区域
                // 这样len可以吃满
                if (info[0] <= a && b <= info[2]) lines.add(new int[]{info[1], info[3]});
            }
            // first - second 就是从小到大排序，大于0就交换的意思
            // 常规匿名写法
            Collections.sort(lines, (l1, l2) -> {
                return l1[0] != l2[0] ? l1[0] - l2[0]: l1[1] - l2[1];
            });
            // 如果cur[0]在r外面，记录结果，重新累加
            // 如果cur[0]在r里面 且cur[1]在r外面 更新r拉长
            long tot = 0, l = -1, r = -1;
            for (int[] cur: lines) {
                if (cur[0] > r) {
                    tot += r - l; // stop
                    l = cur[0];
                    r = cur[1]; // update
                } else if (cur[1] > r) {
                    // accumulate
                    r = cur[1];
                }
            }
            tot += r - l; // rest
            ans += tot * len;
            ans %= MOD;
        }
        return (int) ans;
    }
}
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

1.对List的排序要用Collections的
2.匿名函数的排序使用 first - second就是从小到大的意思
3.int只到31位, long到64位
4.二维数组的定义：List lines = new ArrayList<>();
5.二维数组的增加：lines.add(new int[]{info[1], info[3]});

总结

当然也可以不用差分数组
可以通过遍历l r的位置实现累计的长度和
但是这种可重叠的累计长度和使用差分数组实现也比较好理解