1314_矩阵区域和

难度：中等

题目

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

  • i - k <= r <= i + k,
  • j - k <= c <= j + k 且
  • (r, c) 在矩阵内。

示例

示例一：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例二：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

提示

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100

解题

用前缀和的方法可以减少重复计算

首先计算前缀和 sum 数组， sum[i, j] = sum[i-1][j]+sum[i][j-1]+mat[i-1][j-1]-sum[i-1][j-1]

1
2
3
4
5
6
int[][] sum = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i-1][j-1];
  }
}

然后对每个位置计算和，区域 [(x1,y1),(x2,y2)]的和为 sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1]

注意边界处理

1
2
3
4
5
6
7
for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) {
    int x1 = Math.max(0,i-k), y1 = Math.max(0,j-k);
    int x2 = Math.min(m,i+k+1), y2 = Math.min(n,j+k+1);
    ans[i][j] = sum[x2][y2] - sum[x2][y1] - sum[x1][y2] + sum[x1][y1];
  }
}

组合起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[][] matrixBlockSum(int[][] mat, int k){
  int m = mat.length, n = mat[0].length;
  int[][] ans = new int[m][n];
  int[][] sum = new int[m+1][n+1];
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i-1][j-1];
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      int x1 = Math.max(0,i-k), y1 = Math.max(0,j-k);
      int x2 = Math.min(m,i+k+1), y2 = Math.min(n,j+k+1);
      ans[i][j] = sum[x2][y2] - sum[x2][y1] - sum[x1][y2] + sum[x1][y1];
    }
  }
  return ans;
}