力扣leetcode 850. 矩形面积 II 【困难】

ps: 昨天同事离职聚餐搞太晚了，今天补上。。。

题目链接与描述

https://leetcode.cn/problems/rectangle-area-ii/
我们给出了一个（轴对齐的）二维矩形列表 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
矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。

关键词：扫描线

不考虑重合 很容易想到把区域切分为1等分的矩形，求到y轴长度，然后累加即可得到结果

方法一：

运行截图

代码

{
		// 不考虑重合 很容易想到把区域切分为1等分的矩形，求到y轴长度，然后累加即可得到结果
		// 首先数值需要取模
		long mod = (int) 1e9 + 7;
		// 获得
		List<Integer> xList = new ArrayList<>();
		// 拿到x轴的点集合
		for (int[] info : rectangles) {
			xList.add(info[0]);
			xList.add(info[2]);
		}
		// 排序
		Collections.sort(xList);
		long ans = 0;
		// 从1开始拿到
		for (int i = 1; i < xList.size(); i++) {
			int beforeX = xList.get(i - 1), currentX = xList.get(i), len = currentX - beforeX;
			// 因为有重叠，所以可能存在
			if (len == 0) {
				continue;
			}
			// 然后拿到在这段区域内的 y轴 线段数组
			List<int[]> inYLine = new ArrayList<>();
			for (int[] info : rectangles) {
				// 如果是包含了当前这段则添加进来
				if (info[0] <= beforeX && currentX <= info[2]) {
					inYLine.add(new int[]{info[1], info[3]});
				}
			}
			// 排序，左下角没有重合则先比左下角y，如果重合则比较右上角
			Collections.sort(inYLine, (l1, l2) -> l1[0] != l2[0] ? l1[0] - l2[0] : l1[1] - l2[1]);
			// 加上总面积
			long total = 0, left = -1, right = -1;
			// 循环所有在x轴区域内的y轴线
			for (int[] yRange : inYLine) {
				// 左小角大于上一个右上角表示没有重叠
				if (yRange[0] > right) {
					// 记录x段内的总长度为右上角y减去左下角y
					total += right - left;
					// 赋值记录
					left = yRange[0];
					right = yRange[1];
				} else if (yRange[1] > right) {
					// 如果左下角小于等于上一个右上角 && 右上角大于上一个右上角则不用重复计算
					right = yRange[1];
				}
			}
			// 因为累加是延后一步，所以要再计算一下
			total += right - left;
			// 然后 x 乘 y 得到矩形
			ans += total * 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
49
50
51
52
53
54
55
56
57
58

结尾

欢迎评论区交流，每日打卡，冲冲冲！！！