矩形面积 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 <= 200rectanges[i].length = 40 <= xi1, yi1, xi2, yi2 <= 109
代码结果
运行时间: 36 ms, 内存: 16.3 MB
/*
思路：
1. 使用流处理来简化集合操作和排序。
2. 保持与传统Java代码相同的逻辑，主要使用流来管理事件和Y坐标集合。
3. 使用扫描线算法计算覆盖面积。
*/
import java.util.*;
import java.util.stream.Collectors;
public class RectangleAreaStream {
private static final int MOD = 1000000007;
public int rectangleArea(int[][] rectangles) {
List<int[]> events = Arrays.stream(rectangles)
.flatMap(rect -> Stream.of(
new int[]{rect[0], rect[1], rect[3], 1}, // left edge
new int[]{rect[2], rect[1], rect[3], -1} // right edge
))
.sorted(Comparator.comparingInt(a -> a[0]))
.collect(Collectors.toList());
List<Integer> yList = Arrays.stream(rectangles)
.flatMapToInt(rect -> IntStream.of(rect[1], rect[3]))
.distinct()
.sorted()
.boxed()
.collect(Collectors.toList());
int[] active = new int[yList.size()];
long prevX = 0;
long area = 0;
for (int[] event : events) {
int x = event[0], y1 = event[1], y2 = event[2], type = event[3];
long yCover = 0;
for (int j = 0; j < yList.size() - 1; ++j) {
if (active[j] > 0) {
yCover += yList.get(j + 1) - yList.get(j);
}
}
area = (area + yCover * (x - prevX)) % MOD;
prevX = x;
for (int j = 0; j < yList.size(); ++j) {
if (y1 <= yList.get(j) && yList.get(j) < y2) {
active[j] += type;
}
}
}
return (int) area;
}
}
解释
方法:
该题解的思路是利用扫描线算法。首先将所有矩形的左右边界x坐标去重并排序，建立x坐标到索引的映射。然后遍历每个矩形，将其在x方向上覆盖的区间内的每个位置记录下该矩形在y方向上的区间。接着对于x方向每个分割后的小区间，将其包含的y区间按起点排序，然后用类似合并区间的方法计算出y方向覆盖的长度。最后将所有小矩形区域的面积累加起来即可得到最终结果。
时间复杂度:
O(n^2logn)
空间复杂度:
O(n^2)
代码细节讲解
🦆
扫描线算法中，如何处理重叠的矩形以确保每个区域只被计算一次？
▷🦆
为什么需要将所有x坐标去重并排序？去重和排序对算法的影响是什么？
▷🦆
代码中的`cnt`数组是如何使用的？它在算法中扮演了什么角色？
▷🦆
为什么在处理y区间时需要先对其按起点进行排序？
▷