题目描述
You are given a 2D integer array grid of size m × n, and an integer k.
In one operation, you can:
- Select any
k x k submatrix of grid, and - Increment all elements inside that submatrix by 1.
Return the minimum number of operations required to make all elements in the grid equal. If it is not possible, return -1.
A submatrix (x1, y1, x2, y2) is a matrix that forms by choosing all cells matrix[x][y] where x1 <= x <= x2 and y1 <= y <= y2.
Example 1:
Input: grid = [[3,3,5],[3,3,5]], k = 2
Output: 2
Explanation:
Choose the left 2 x 2 submatrix (covering the first two columns) and apply the operation twice.
- After 1 operation:
[[4, 4, 5], [4, 4, 5]] - After 2 operations:
[[5, 5, 5], [5, 5, 5]]
All elements become equal to 5. Thus, the minimum number of operations is 2.
Example 2:
Input: grid = [[1,2],[2,3]], k = 1
Output: 4
Explanation:
Since k = 1, each operation increments a single cell grid[i][j] by 1. To make all elements equal, the final value must be 3.
- Increase
grid[0][0] = 1 to 3, requiring 2 operations. - Increase
grid[0][1] = 2 to 3, requiring 1 operation. - Increase
grid[1][0] = 2 to 3, requiring 1 operation.
Thus, the minimum number of operations is 2 + 1 + 1 + 0 = 4.
Constraints:
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;
}
|