小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场。
经过不断的勘测记录，小扣将所有力场的分布都记录了下来。forceField[i] = [x,y,side] 表示第 i 片力场将覆盖以坐标
(x,y) 为中心，边长为 side 的正方形区域。 若任意一点的 力场强度 等于覆盖该点的力场数量，请求出在这片地带中 力场强度
最强处的 力场强度。 注意： - 力场范围的边缘同样被力场覆盖。 示例 1： >输入： >forceField = [[0,0,1],[1,0,1]] > >输出：2 > >解释：如图所示，（0.5, 0) 处力场强度最强为 2，
（0.5，-0.5）处力场强度同样是 2。 {:width=400px} 示例 2： >输入： >forceField = [[4,4,6],[7,5,3],[1,6,2],[5,6,3]] > >输出：3 > >解释：如下图所示，
forceField[0]、forceField[1]、forceField[3] 重叠的区域力场强度最大，返回 3
{:width=500px} 提示： - 1 <= forceField.length <= 100 -
forceField[i].length == 3 - 0 <= forceField[i][0], forceField[i][1] <= 10^9 - 1 <= forceField[i][2] <= 10^9
本题视频讲解
见【力扣杯2023春·个人赛】 第三题。
思路
- 统计所有左下和右上坐标，由于会出现 0.5，可以将坐标乘 2。
- 离散化横纵坐标。
- 二维差分，具体见视频讲解。
- 用二维前缀和复原，计算最大值。
[sol1-Python3]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
| class Solution:
def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:
x_set = set()
y_set = set()
for i, j, side in forceField:
x_set.add(2 * i - side)
x_set.add(2 * i + side)
y_set.add(2 * j - side)
y_set.add(2 * j + side)
xs = sorted(x_set)
ys = sorted(y_set)
n, m = len(xs), len(ys)
diff = [[0] * (m + 2) for _ in range(n + 2)]
for i, j, side in forceField:
r1 = bisect_left(xs, 2 * i - side)
r2 = bisect_left(xs, 2 * i + side)
c1 = bisect_left(ys, 2 * j - side)
c2 = bisect_left(ys, 2 * j + side)
diff[r1 + 1][c1 + 1] += 1
diff[r1 + 1][c2 + 2] -= 1
diff[r2 + 2][c1 + 1] -= 1
diff[r2 + 2][c2 + 2] += 1
ans = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]
ans = max(ans, diff[i][j])
return ans
|
[sol1-Java]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
| class Solution {
public int fieldOfGreatestBlessing(int[][] forceField) {
int nf = forceField.length, k = 0;
long[] xs = new long[nf * 2], ys = new long[nf * 2];
for (var f : forceField) {
long i = f[0], j = f[1], side = f[2];
xs[k] = 2 * i - side;
xs[k + 1] = 2 * i + side;
ys[k++] = 2 * j - side;
ys[k++] = 2 * j + side;
}
xs = unique(xs);
ys = unique(ys);
int n = xs.length, m = ys.length;
var diff = new int[n + 2][m + 2];
for (var f : forceField) {
long i = f[0], j = f[1], side = f[2];
int r1 = Arrays.binarySearch(xs, 2 * i - side);
int r2 = Arrays.binarySearch(xs, 2 * i + side);
int c1 = Arrays.binarySearch(ys, 2 * j - side);
int c2 = Arrays.binarySearch(ys, 2 * j + side);
++diff[r1 + 1][c1 + 1];
--diff[r1 + 1][c2 + 2];
--diff[r2 + 2][c1 + 1];
++diff[r2 + 2][c2 + 2];
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++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;
}
private long[] unique(long[] a) {
Arrays.sort(a);
int k = 0;
for (int i = 1; i < a.length; i++)
if (a[k] != a[i])
a[++k] = a[i];
return Arrays.copyOf(a, k + 1);
}
}
|
[sol1-C++]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
| class Solution {
public:
int fieldOfGreatestBlessing(vector<vector<int>> &forceField) {
vector<long long> xs, ys;
for (auto &f: forceField) {
long long i = f[0], j = f[1], side = f[2];
xs.push_back(2 * i - side);
xs.push_back(2 * i + side);
ys.push_back(2 * j - side);
ys.push_back(2 * j + side);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
int n = xs.size(), m = ys.size(), diff[n + 2][m + 2];
memset(diff, 0, sizeof(diff));
for (auto &f: forceField) {
long long i = f[0], j = f[1], side = f[2];
int r1 = lower_bound(xs.begin(), xs.end(), 2 * i - side) - xs.begin();
int r2 = lower_bound(xs.begin(), xs.end(), 2 * i + side) - xs.begin();
int c1 = lower_bound(ys.begin(), ys.end(), 2 * j - side) - ys.begin();
int c2 = lower_bound(ys.begin(), ys.end(), 2 * j + side) - ys.begin();
++diff[r1 + 1][c1 + 1];
--diff[r1 + 1][c2 + 2];
--diff[r2 + 2][c1 + 1];
++diff[r2 + 2][c2 + 2];
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
ans = max(ans, diff[i][j]);
}
}
return ans;
}
};
|
[sol1-Golang]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
| func fieldOfGreatestBlessing(forceField [][]int) (ans int) {
var xs, ys []int
for _, f := range forceField {
i, j, side := f[0], f[1], f[2]
xs = append(xs, 2*i-side, 2*i+side)
ys = append(ys, 2*j-side, 2*j+side)
}
unique := func(a []int) []int {
sort.Ints(a)
k := 0
for _, x := range a[1:] {
if a[k] != x {
k++
a[k] = x
}
}
return a[:k+1]
}
xs = unique(xs)
ys = unique(ys)
n, m := len(xs), len(ys)
diff := make([][]int, n+2)
for i := range diff {
diff[i] = make([]int, m+2)
}
for _, f := range forceField {
i, j, side := f[0], f[1], f[2]
r1 := sort.SearchInts(xs, 2*i-side)
r2 := sort.SearchInts(xs, 2*i+side)
c1 := sort.SearchInts(ys, 2*j-side)
c2 := sort.SearchInts(ys, 2*j+side)
diff[r1+1][c1+1]++
diff[r1+1][c2+2]--
diff[r2+2][c1+1]--
diff[r2+2][c2+2]++
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]
ans = max(ans, diff[i][j])
}
}
return
}
func max(a, b int) int { if a < b { return b }; return a }
|
复杂度分析
- 时间复杂度：\mathcal{O}(n^2)，其中 n 为 forceField 的长度。
- 空间复杂度：\mathcal{O}(n^2)。
