二维前缀和可以应用在二维数组元素和计算中。

代码模板

  1. 首先处理原来的数组，生成二位前缀和数组

    1. m,n=len(mat),len(mat[0])
    2. P=[[0 for i in range(n+1)] for j in range(m+1)]
    3. for i in range(1,m+1):
    4.  for j in range(1,n+1):
    5.      P[i][j]=P[i-1][j]+P[i][j-1]+mat[i-1][j-1]-P[i-1][j-1]

  2. 定义计算范围内元素和的函数

    1. def areaRect(x1,y1,x2,y2):
    2.  return P[x2][y2]-P[x1-1][y2]-P[x2][y1-1]+P[x1-1][y1-1]

  3. 进行循环遍历处理，这里可以形成自己的思维。
    因为二维前缀和数组的维度比原数组大①，所以容易产生混淆：

    • 在遍历数组的时候，我们都使用在原来数组中的坐标
    • 如果涉及到边长，我们使用真实边长；注意新的位置有时需要减一i+r-1
    • 传入二维前缀和数组的时候，再把每一个位置都加上①
      1. # 1314 矩阵和
      2. # i - K <= r <= i + K, j - K <= c <= j + K
      3. for i in range(m):
      4. for j in range(n):
      5.    right_x=i+K if i+K<m else m-1
      6.    right_y=j+K if j+K<n else n-1
      7.    left_x=i-K if i-K>=0 else 0
      8.    left_y=j-K if j-K>=0 else 0
      9.    #左侧+1就从1开始了，这样还对吗？
      10.    #还是正确的，这样的思路更容易想到
      11.    #找到原来的位置，然后+1修改成我们的增广矩阵的位置
      12.    mat[i][j]=areaRect(left_x+1,left_y+1,right_x+1,right_y+1)
  1. # 1292 正方形区域的最大边长
  2. maxR,r=min(m,n),0
  3. for i in range(m):
  4.     for j in range(n):
  5.         for c in range(r+1,maxR+1):
  6.             #还是使用原来矩阵和新矩阵的映射
  7.             #在传入函数中计算之前都是原来矩阵
  8.             if i+c-1<m and j+c-1<n and areaRect(i+1,j+1,i+c,j+c)<=threshold:
  9.                 r+=1
  10.                 else:
  11.                     break

相关习题

1292. 元素和小于等于阈值的正方形的最大边长
1314. 矩阵区域和