矩阵区域和

题目描述：

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

思路:

时间复杂度：O(n^2),空间复杂度O(n^2)

得先求得二维矩阵前缀和的方法

代码:

func matrixBlockSum(mat [][]int, k int) [][]int {
    m,n := len(mat), len(mat[0])
    dp := make([][]int, m+1)
    res := make([][]int, m)
    for i:=0;i<=m;i++{
        dp[i] = make([]int, n+1)
    }
    for i:=0;i<m;i++{
        res[i] = make([]int, n)
    }
    for i:=1;i<=m;i++{
        for j:=1;j<=n;j++{
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]+ mat[i-1][j-1]
        }
    }

    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            li,lj,ri,rj := max(0,i-k),max(0,j-k), min(m,i+k+1),min(n, j+k+1)
            res[i][j] = dp[ri][rj] - dp[li][rj] - dp[ri][lj] + dp[li][lj]
        }
    }
    return res
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b 
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b 
}

代码效率：

执行用时：8 ms, 在所有 Go 提交中击败了81.40%的用户
内存消耗：6.1 MB, 在所有 Go 提交中击败了46.51%的用户