问题

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

题解

如果采用暴力法，每个格子直接计算，会发现存在大量的重复计算，可先构造一个矩阵dp，原矩阵是mat，dp[i,j]表示从矩阵左上角mat[0,0]到右下角mat[i,j]这个范围构成的矩阵所有元素之和。
该矩阵可看作是一个左上角是(0,0)，右下角是(i,j)围成的矩形的面积，得到该矩阵后，就可以采用面积差来计算任意矩形的面积。
比如下图求左上角(2,1)和右下角(4,3)构成的蓝色部分，可通过由(0,0)到(4,3)的面积减去绿色部分(0,0)到(1,3)，减去黄色部分(0,0)到(4,0)，当然红色部分(0,0)到(1,0)是2个矩形相交的部分，会被减去2次，所以还得增加1次。而这几部分矩形都是从(0,0)作为左上角的，面积都是已知的存储在dp中。

1
(0,0)		 2
(0,1)		 3
(0,2)		 4
(0,3)		 5
(0,4)
6
(1,0)		 7
(1,1)		 8
(1,2)		 9
(1,3)		 0
(1,4)
1
(2,0)		 2
(2,1)		 3
(2,2)		 4
(2,3)		 5
(2,4)
6
(3,0)		 7
(3,1)		 8
(3,2)		 9
(3,3)		 0
(3,4)
1
(4,0)		 2
(4,1)		 3
(4,2)		 4
(4,3)		 5
(4,4)

用动态规划法求dp

每个dp都可以看作是上边的dp加上左边的dp，减去相交的部分，同时还要加上这个dp本身在矩阵中的值
dp[i][j]=mat[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

原矩阵
1
(0,0)		 2
(0,1)		 3
(0,2)
4
(1,0)		 5
(1,1)		 6
(1,2)
7
(2,0)		 8
(2,1)		 9
(2,2)
dp矩阵
1
(0,0)		 3
(0,1)		 6
(0,2)
5
(1,0)		 12
(1,1)		 ?
(i,j)
?
(2,0)		 ?
(2,1)		 ?
(2,2)

我这里为了避免边界检查，将dp在原矩阵上扩展了一行和一列，待计算完毕后再恢复回来

1
2
3
4
5
6
7
8
9
r=len(mat)
c=len(mat[0])
dp=[[0 for _ in range(c+1)] for _ in range(r+1)]
for i in range(1,r+1):
    for j in range(1,c+1):
        dp[i][j]=mat[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
dp.pop(0)
for d in dp:
    d.pop(0)

当然你也可以先特殊处理第一行和第一列，再执行同样的计算。

1
2
3
4
5
6
7
8
9
dp=[[0 for _ in range(c)] for _ in range(r)]
dp[0][0] = mat[0][0]
for j in range(1,c):       #处理第一行
    dp[0][j]=mat[0][j]+dp[0][j-1]
for i in range(1,r):       #处理第一列
    dp[i][0]=mat[i][0]+dp[i-1][0]
for i in range(1,r):
    for j in range(1,c):
        dp[i][j]=mat[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

根据dp求每个格子的值

以每个格子作为中心点，根据半径可求得矩形的左上角start和右下角end，根据这2个点就可以得到上面说的4个矩形的面积了，当然还需要作边界检查，还有只有当start点既不在第一行也不在第一列时才会产生2个需要减去的矩形，换句话说，当start点在第一行或者第一列时，只会产生一个矩形或者没有。只有当出现2个矩形的时候，才会出现相交，同时这个相交部分会被减去2次，所以还得增加1次相交部分。

1
2
3
4
5
6
7
res=[[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
    for j in range(c):
        start=(max(i-K,0),max(j-K,0))
        end=(min(i+K,r-1),min(j+K,c-1))
        res[i][j]=dp[end[0]][end[1]] - (0 if start[0]==0 else dp[start[0]-1][end[1]]) - (0 if start[1]==0 else dp[end[0]][start[1]-1])+ (0 if start[0]==0 or start[1]==0 else dp[start[0]-1][start[1]-1])
return res

时间复杂度$ O(MN) $