850. Rectangle Area II
850. Rectangle Area II
题目: https://leetcode.com/problems/rectangle-area-ii/
难度: Hard
题意：
- 给n个矩阵，求这n个矩阵覆盖的区域面积有多大
思路：
- 把x坐标和y坐标id化，将n个矩阵覆盖的区域分成r*c个小矩阵，这些小矩阵的距离都可以不相等
- 遍历所有的矩阵，把这些小矩阵填充满
- 遍历小矩阵，统计面积
- 复杂度是o(n^3)
- 这个题目可以将x坐标id化后，构建线段树来查询和更新面积区域，复杂度可以降为o(n^2logn)，当n>=1000使用
代码：
class Solution {
private int[] setToArray(TreeSet<Integer> set) {
int[] ret = new int[set.size()];
int idx = 0;
for (Integer e: set) {
ret[idx++] = e;
}
return ret;
}
private static int MOD = 1000000007;
public int rectangleArea(int[][] rectangles) {
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 0;i < rectangles.length;i++) {
set.add(rectangles[i][0]);
set.add(rectangles[i][2]);
}
int[] x = setToArray(set);
set.clear();
for (int i = 0;i < rectangles.length;i++) {
set.add(rectangles[i][1]);
set.add(rectangles[i][3]);
}
int[] y = setToArray(set);
boolean[][] area = new boolean[x.length][y.length];
for (int i = 0;i < x.length;i++) {
for (int j = 0;j < y.length;j++) {
area[i][j] = false;
}
}
for (int i = 0;i < rectangles.length;i++) {
int lx = Arrays.binarySearch(x, rectangles[i][0]);
int rx = Arrays.binarySearch(x, rectangles[i][2]);
int ly = Arrays.binarySearch(y, rectangles[i][1]);
int ry = Arrays.binarySearch(y, rectangles[i][3]);
for (int j = lx;j < rx;j++) {
for (int k = ly;k < ry;k++) {
area[j][k] = true;
}
}
}
int ret = 0;
for (int i = 0;i < x.length;i++) {
for (int j = 0;j < y.length;j++) {
if (area[i][j]) {
ret += (long)(x[i + 1] - x[i]) * (y[j + 1] - y[j]) % MOD;
if (ret >= MOD) {
ret -= MOD;
}
}
}
}
return ret;
}
}
