当前位置：首页 > article >正文

【数据结构-二维前缀和】力扣1314. 矩阵区域和

article 2024/11/17 3:45:03

给你一个 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

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> answer(m, vector<int>(n));
        vector<vector<int>> sums(m+1, vector<int>(n+1));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + mat[i][j];
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int m2 = i+k < m ? i+k : m-1;
                int n2 = j+k < n ? j+k : n-1;
                int m1 = i-k >= 0 ? i-k : 0;
                int n1 = j-k >= 0 ? j-k : 0;
                answer[i][j] = sums[m2+1][n2+1] - sums[m1][n2+1] - sums[m2+1][n1] + sums[m1][n1];
            }
        }
        return answer;
    }
};