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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
public static int fieldOfGreatestBlessing(int[][] fields) {
int n = fields.length;
// 收集所有矩形的边界坐标
long[] xs = new long[n << 1];
long[] ys = new long[n << 1];
for (int i = 0, k = 0, p = 0; i < n; i++) {
long x = fields[i][0];
long y = fields[i][1];
long r = fields[i][2];
// 坐标乘2避免小数，左边界和右边界
xs[k++] = (x << 1) - r;
xs[k++] = (x << 1) + r;
ys[p++] = (y << 1) - r;
ys[p++] = (y << 1) + r;
}
// 坐标压缩：排序去重
int sizex = sort(xs);
int sizey = sort(ys);
// 二维差分数组
int[][] diff = new int[sizex + 2][sizey + 2];
// 对每个矩形在差分数组上标记
for (int i = 0; i < n; i++) {
long x = fields[i][0];
long y = fields[i][1];
long r = fields[i][2];
// 找到压缩后的坐标编号
int a = rank(xs, (x << 1) - r, sizex);
int b = rank(ys, (y << 1) - r, sizey);
int c = rank(xs, (x << 1) + r, sizex);
int d = rank(ys, (y << 1) + r, sizey);
// 二维差分标记
add(diff, a, b, c, d);
}
// 还原真实覆盖次数并求最大值
int ans = 0;
for (int i = 1; i < diff.length; i++) {
for (int j = 1; j < diff[0].length; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
ans = Math.max(ans, diff[i][j]);
}
}
return ans;
}
// 排序去重，返回有效长度
public static int sort(long[] nums) {
Arrays.sort(nums);
int size = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[size - 1]) {
nums[size++] = nums[i];
}
}
return size;
}
// 二分查找坐标对应的压缩编号
public static int rank(long[] nums, long v, int size) {
int l = 0, r = size - 1;
int ans = 0;
while (l <= r) {
int m = (l + r) / 2;
if (nums[m] >= v) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans + 1; // 编号从1开始
}
// 二维差分标记矩形区域
public static void add(int[][] diff, int a, int b, int c, int d) {
diff[a][b] += 1;
diff[c + 1][d + 1] += 1;
diff[c + 1][b] -= 1;
diff[a][d + 1] -= 1;
}
|
