原文链接: https://leetcode-cn.com/problems/matrix-block-sum

英文原文

Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:

• i - k <= r <= i + k,
• j - k <= c <= j + k, and
• (r, c) is a valid position in the matrix.

 

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

 

Constraints:

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

中文题目

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

通过代码

高赞题解

预备知识

本题需要用到一些二维前缀和（Prefix Sum）的知识，它是一维前缀和的延伸。

具体可以参考力扣 1292 题的官方题解 中的「预备知识」和「注意事项」部分。

方法一：二维前缀和

我们用数组 P 表示数组 mat 的二维前缀和，P 的维数为 (m + 1) * (n + 1)，其中 P[i][j] 表示数组 mat 中以 (0, 0) 为左上角，(i - 1, j - 1) 为右下角的矩形子数组的元素之和。

题目需要对数组 mat 中的每个位置，计算以 (i - K, j - K) 为左上角，(i + K, j + K) 为右下角的矩形子数组的元素之和，我们可以在前缀和数组的帮助下，通过：

sum = P[i + K + 1][j + K + 1] - P[i - K][j + K + 1] - P[i + K + 1][j - K] + P[i - K][j - K]

得到元素之和。注意到 i + K + 1、j + K - 1、i - K 和 j - K 这些下标有可能不在矩阵内，因此对于所有的横坐标，我们需要将其规范在 [0, m] 的区间内；对于所有的纵坐标，我们需要将其规范在 [0, n] 的区间内。具体地：

• i + K + 1 和 j + K - 1 分别可能超过 m 和 n，因此我们需要对这两个坐标与 m 和 n 取较小值，忽略不在矩阵内的部分；

• i - K 和 j - K 可能小于 0，因此我们需要对这两个坐标与 0 取较大值，忽略不在矩阵内的部分。

更一般的做法是，我们对所有的横坐标与 m 取较小值，纵坐标与 n 取较小值，再将所有坐标与 0 取较大值，就可以将这些坐标规范在前缀和数组 P 的范围内。

[sol1-C++]
class Solution {
public:
    int get(const vector<vector<int>>& pre, int m, int n, int x, int y) {
        x = max(min(x, m), 0);
        y = max(min(y, n), 0);
        return pre[x][y];
    }
    
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> P(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[i][j] = get(P, m, n, i + K + 1, j + K + 1) - get(P, m, n, i - K, j + K + 1) - get(P, m, n, i + K + 1, j - K) + get(P, m, n, i - K, j - K);
            }
        }
        return ans;
    }
};

[sol1-Python3]
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        P = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]
        
        def get(x, y):
            x = max(min(x, m), 0)
            y = max(min(y, n), 0)
            return P[x][y]

        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);
        return ans

复杂度分析

• 时间复杂度：$O(MN)$。

• 空间复杂度：$O(MN)$。

统计信息

通过次数	提交次数	AC比率
13255	17771	74.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言