文章目录
- 1.题目
- 2.思路
- 3.代码
1.题目
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)在矩阵内。
示例 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]]
2.思路
每个元素表示从矩阵左上角 (0, 0) 到当前位置的矩形区域的所有元素的和。然后，对于每个元素 (i, j)，根据前缀和矩阵快速计算以 (i, j) 为中心、半径为 k 的矩形区域的和，其中利用四个前缀和值来快速计算任意矩形的和
3.代码
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size();int n = mat[0].size();// 创建前缀和矩阵，大小为 (m+1)x(n+1) 方便处理边界vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 计算前缀和矩阵for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] +dp[i][j - 1] - dp[i - 1][j - 1];}}// 创建结果矩阵vector<vector<int>> answer(m, vector<int>(n, 0));// 计算每个位置的块和for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {// 确定块的边界int x1 = max(0, i - k);int y1 = max(0, j - k);int x2 = min(m - 1, i + k);int y2 = min(n - 1, j + k);// 利用前缀和计算块和answer[i][j] = dp[x2 + 1][y2 + 1] -dp[x1][y2 + 1] - dp[x2 + 1][y1] +dp[x1][y1];}}return answer;}
};
