题目描述
给定一个大小为 m × n 的 2 维整数数组 grid，和一个整数 k。
在一次操作中，你可以：
- 选择
grid 任意 k x k 的 子矩阵，并且 - 将该子矩阵中的所有元素加 1。
返回使网格中所有元素相等所需的最少操作次数。如果不可能，请返回 -1。
一个子矩阵 (x1, y1, x2, y2) 是由所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的矩阵元素 matrix[x][y] 组成的矩阵。
示例 1：
输入：grid = [[3,3,5],[3,3,5]], k = 2
输出：2
解释：
选择左边的 2 x 2 子矩阵（覆盖前两列）并应用该操作两次。
- 在 1 次操作后：
[[4, 4, 5], [4, 4, 5]] - 在 2 次操作后：
[[5, 5, 5], [5, 5, 5]]
所有元素都变为 5。因此，所需的最小操作次数是 2。
示例 2：
输入：grid = [[1,2],[2,3]], k = 1
输出：4
解释：
由于 k = 1，每次操作将单个单元格 grid[i][j] 的值加1。要使所有元素相等，最终值必须为 3。
- 增加
grid[0][0] = 1 到 3，需要 2 次操作。 - 增加
grid[0][1] = 2 到 3，需要 1 次操作。 - 增加
grid[1][0] = 2 到 3，需要 1 次操作。
因此，所需的最小操作次数是 2 + 1 + 1 + 0 = 4。
提示：
1 <= m == grid.length <= 10001 <= n == grid[i].length <= 1000-105 <= grid[i][j] <= 1051 <= k <= min(m, n)
解法
方法一：二维差分 + 贪心
由于操作只能增加元素的值，因此最终网格的所有元素必须等于某个目标值 \(T\)，且 \(T \ge \max(\textit{grid})\)。
从左上角 \((0, 0)\) 开始遍历网格。对于任意位置 \((i, j)\)，如果它当前的数值小于 \(T\)，由于后续的操作（以更靠右或更靠下的位置为左上角的操作）都无法覆盖到 \((i, j)\)，因此必须在当前位置执行 \(T - \text{current\_val}\) 次以 \((i, j)\) 为左上角的 \(k \times k\) 增加操作。
如果每次执行操作都遍历 \(k \times k\) 区域，复杂度将达到 \(O(m \cdot n \cdot k^2)\)。我们可以使用二维差分数组 \(\textit{diff}\) 来记录操作。通过实时维护 \(\textit{diff}\) 的二维前缀和，我们可以在 \(O(1)\) 时间内获取当前位置的累计增量，并在 \(O(1)\) 时间内更新一个 \(k \times k\) 区域的未来影响。
通常情况下 \(T = \max(\textit{grid})\) 即可。但在某些 \(k \times k\) 覆盖重叠的情况下，较小的 \(T\) 可能导致中间位置被动增加后超过 \(T\)。根据数学一致性，若 \(T = \max(\textit{grid})\) 和 \(T = \max(\textit{grid}) + 1\) 均不可行，则该网格无法通过 \(k \times k\) 操作变平。
时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)，其中 \(m\) 和 \(n\) 分别是网格的行数和列数。
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 | class Solution:
def minOperations(self, grid: list[list[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
mx = max(max(row) for row in grid)
def check(target: int) -> int:
diff = [[0] * (n + 2) for _ in range(m + 2)]
total_ops = 0
for i, row in enumerate(grid, 1):
for j, val in enumerate(row, 1):
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
cur_val = val + diff[i][j]
if cur_val > target:
return -1
if cur_val < target:
if i + k - 1 > m or j + k - 1 > n:
return -1
needed = target - cur_val
total_ops += needed
diff[i][j] += needed
diff[i + k][j] -= needed
diff[i][j + k] -= needed
diff[i + k][j + k] += needed
return total_ops
for t in range(mx, mx + 2):
res = check(t)
if res != -1:
return res
return -1
|
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 | class Solution {
int[][] grid;
int m, n, k;
public long minOperations(int[][] grid, int k) {
this.grid = grid;
this.k = k;
this.m = grid.length;
this.n = grid[0].length;
int mx = Integer.MIN_VALUE;
for (int[] row : grid) {
for (int v : row) {
mx = Math.max(mx, v);
}
}
for (int t = mx; t <= mx + 1; t++) {
long res = check(t);
if (res != -1) {
return res;
}
}
return -1;
}
private long check(int target) {
long[][] diff = new long[m + 2][n + 2];
long totalOps = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
long cur = grid[i - 1][j - 1] + diff[i][j];
if (cur > target) {
return -1;
}
if (cur < target) {
if (i + k - 1 > m || j + k - 1 > n) {
return -1;
}
long need = target - cur;
totalOps += need;
diff[i][j] += need;
diff[i + k][j] -= need;
diff[i][j + k] -= need;
diff[i + k][j + k] += need;
}
}
}
return totalOps;
}
}
|
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 | class Solution {
public:
long long minOperations(vector<vector<int>>& grid, int k) {
int m = grid.size();
int n = grid[0].size();
int mx = grid[0][0];
for (auto& row : grid) {
for (int val : row) {
mx = max(mx, val);
}
}
auto check = [&](int target) -> long long {
vector<vector<long long>> diff(m + 2, vector<long long>(n + 2, 0));
long long total_ops = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
long long cur_val = grid[i - 1][j - 1] + diff[i][j];
if (cur_val > target) {
return -1;
}
if (cur_val < target) {
if (i + k - 1 > m || j + k - 1 > n) {
return -1;
}
long long needed = target - cur_val;
total_ops += needed;
diff[i][j] += needed;
diff[i + k][j] -= needed;
diff[i][j + k] -= needed;
diff[i + k][j + k] += needed;
}
}
}
return total_ops;
};
for (int t = mx; t <= mx + 1; ++t) {
long long res = check(t);
if (res != -1) {
return res;
}
}
return -1;
}
};
|
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 | func minOperations(grid [][]int, k int) int64 {
m, n := len(grid), len(grid[0])
maxVal := grid[0][0]
for _, row := range grid {
maxVal = max(maxVal, slices.Max(row))
}
check := func(target int) int64 {
diff := make([][]int64, m+2)
for i := range diff {
diff[i] = make([]int64, n+2)
}
var totalOps int64
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]
curVal := int64(grid[i-1][j-1]) + diff[i][j]
if curVal > int64(target) {
return -1
}
if curVal < int64(target) {
if i+k-1 > m || j+k-1 > n {
return -1
}
needed := int64(target) - curVal
totalOps += needed
diff[i][j] += needed
diff[i+k][j] -= needed
diff[i][j+k] -= needed
diff[i+k][j+k] += needed
}
}
}
return totalOps
}
for t := maxVal; t <= maxVal+1; t++ {
if res := check(t); res != -1 {
return res
}
}
return -1
}
|
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 | function minOperations(grid: number[][], k: number): number {
const m = grid.length;
const n = grid[0].length;
let maxVal = grid[0][0];
for (const row of grid) {
for (const val of row) {
maxVal = Math.max(maxVal, val);
}
}
const check = (target: number): number => {
const diff: number[][] = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));
let totalOps = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
const curVal = grid[i - 1][j - 1] + diff[i][j];
if (curVal > target) return -1;
if (curVal < target) {
if (i + k - 1 > m || j + k - 1 > n) return -1;
const needed = target - curVal;
totalOps += needed;
diff[i][j] += needed;
diff[i + k][j] -= needed;
diff[i][j + k] -= needed;
diff[i + k][j + k] += needed;
}
}
}
return totalOps;
};
for (let t = maxVal; t <= maxVal + 1; t++) {
const res = check(t);
if (res !== -1) return res;
}
return -1;
}
|