Question

1314. 矩阵区域和

English Version

题目描述

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

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

 

示例 1：

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

示例 2：

输入：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

解法

方法一：二维前缀和

本题属于二维前缀和模板题。

我们定义 $s[i][j]$ 表示矩阵 $mat$ 前 $i$ 行，前 $j$ 列的元素和。那么 $s[i][j]$ 的计算公式为：

$$ s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1] $$

这样我们就可以通过 $s$ 数组快速计算出任意矩形区域的元素和。

对于一个左上角坐标为 $(x_1, y_1)$，右下角坐标为 $(x_2, y_2)$ 的矩形区域的元素和，我们可以通过 $s$ 数组计算出来：

$$ s[x_2+1][y_2+1] - s[x_1][y_2+1] - s[x_2+1][y_1] + s[x_1][y_1] $$

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

class Solution:
  def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    s = [[0] * (n + 1) for _ in range(m + 1)]
    for i, row in enumerate(mat, 1):
      for j, x in enumerate(row, 1):
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
    ans = [[0] * n for _ in range(m)]
    for i in range(m):
      for j in range(n):
        x1, y1 = max(i - k, 0), max(j - k, 0)
        x2, y2 = min(m - 1, i + k), min(n - 1, j + k)
        ans[i][j] = (
          s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1]
        )
    return ans

class Solution {
  public int[][] matrixBlockSum(int[][] mat, int k) {
    int m = mat.length;
    int n = mat[0].length;
    int[][] s = new int[m + 1][n + 1];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
      }
    }

    int[][] ans = new int[m][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int x1 = Math.max(i - k, 0);
        int y1 = Math.max(j - k, 0);
        int x2 = Math.min(m - 1, i + k);
        int y2 = Math.min(n - 1, j + k);
        ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    int m = mat.size();
    int n = mat[0].size();

    vector<vector<int>> s(m + 1, vector<int>(n + 1));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
      }
    }

    vector<vector<int>> ans(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int x1 = max(i - k, 0);
        int y1 = max(j - k, 0);
        int x2 = min(m - 1, i + k);
        int y2 = min(n - 1, j + k);
        ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
      }
    }
    return ans;
  }
};

func matrixBlockSum(mat [][]int, k int) [][]int {
  m, n := len(mat), len(mat[0])
  s := make([][]int, m+1)
  for i := range s {
    s[i] = make([]int, n+1)
  }
  for i, row := range mat {
    for j, x := range row {
      s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + x
    }
  }

  ans := make([][]int, m)
  for i := range ans {
    ans[i] = make([]int, n)
  }

  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      x1 := max(i-k, 0)
      y1 := max(j-k, 0)
      x2 := min(m-1, i+k)
      y2 := min(n-1, j+k)
      ans[i][j] = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]
    }
  }

  return ans
}

function matrixBlockSum(mat: number[][], k: number): number[][] {
  const m: number = mat.length;
  const n: number = mat[0].length;

  const s: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
    }
  }

  const ans: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const x1: number = Math.max(i - k, 0);
      const y1: number = Math.max(j - k, 0);
      const x2: number = Math.min(m - 1, i + k);
      const y2: number = Math.min(n - 1, j + k);
      ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
    }
  }

  return ans;
}