[304][中等][动态规划][前缀和] 二维区域和检索 - 矩阵不可变

题目描述

304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例：

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

提示：

• 你可以假设矩阵不可变。

• 会多次调用 sumRegion 方法。

• 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

解题思路

依然沿用前缀和的思路, 只不过由一维扩展到了二维.

使用一个二维数组记录前缀和, 由于是二维数组, 这里的前缀和f(i, j)定义为(0, 0)到(i, j)子矩阵的所有元素之和. 那么在计算前缀和时, 还是需要使用动态规划的方法.

在求f(i, j)之前, 我们已经知道了f(i-1, j-1), f(i-1, j), f(i, j-1)的值, 为了覆盖所有方格, 先求f(i-1, j)和f(i, j-1)之和, 但由于加了两次f(i-1, j-1)部分, 需要减去一次f(i-1, j-1)部分, 最后再加上新的matrix(i, j)的值. 因此状态转移公式如下图中所示.

得到前缀和之后, 就要考虑求解大矩阵中任意位置的子矩阵元素之和的问题. 如下图所示, 求点A到点D确定的子矩形中所有元素之和记为S(A, D), 那么S(A, D)就要从S(O, D)中来. 为了减去红色和粉红色的部分, 就要将S(O, D)减去S(O, E)再减去S(O, F). 由于灰色部分减去了两次, 所以要加上一次S(O, G).

公式如下:

S(A, D) = S(O, G) - S(O, E) - S(O, F) + S(O, G)

另外还有一点需要特别注意. 如果点D的坐标有一个维度为0, 问题就由二维问题降为一维问题, 这种边界情况在计算前缀和以及求解任意两点的结果时都需要考虑. 而同一维的情况一样, 在创建前缀和矩阵时, 在左侧和上方的外围都添加上一圈0, 这样就将所有问题都转化为矩阵内部的问题, 也就不用考虑边缘情况了.

对比使用与不使用这个技巧的代码复杂度.

不使用:

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix_prefix = None
        n, m = None, None
        if matrix:
            n = len(matrix)
            if n:
                m = len(matrix[0])
        if n and m:
            self.matrix_prefix = [[0] * m for _ in range(n)]
            self.matrix_prefix[0][0] = matrix[0][0]
            for i in range(1, n):
                self.matrix_prefix[i][0] = self.matrix_prefix[i - 1][0] + matrix[i][0]
            for j in range(1, m):
                self.matrix_prefix[0][j] = self.matrix_prefix[0][j - 1] + matrix[0][j]
            for i in range(1, n):
                for j in range(1, m):
                    self.matrix_prefix[i][j] = self.matrix_prefix[i][j - 1] + \
                                               self.matrix_prefix[i - 1][j] - \
                                               self.matrix_prefix[i - 1][j - 1] + \
                                               matrix[i][j]


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        if self.matrix_prefix is None:
            return 0

        if row1 == 0 and col1 == 0:
            return self.matrix_prefix[row2][col2]

        if row1 == 0:
            return self.matrix_prefix[row2][col2] - self.matrix_prefix[row2][col1 - 1]

        if col1 == 0:
            return self.matrix_prefix[row2][col2] - self.matrix_prefix[row1 - 1][col2]

        return self.matrix_prefix[row2][col2] - \
               self.matrix_prefix[row1 - 1][col2] - \
               self.matrix_prefix[row2][col1 - 1] + \
               self.matrix_prefix[row1 - 1][col1 - 1]

使用:

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            M, N = 0, 0
        else:
            M, N = len(matrix), len(matrix[0])
        self.preSum = [[0] * (N + 1) for _ in range(M + 1)]
        for i in range(M):
            for j in range(N):
                self.preSum[i + 1][j + 1] = self.preSum[i][j + 1] + self.preSum[i + 1][j]  - self.preSum[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.preSum[row2 + 1][col2 + 1] - self.preSum[row2 + 1][col1] - self.preSum[row1][col2 + 1] + self.preSum[row1][col1]

相关题目

• [303][简单][动态规划][前缀和] 区域和检索 - 数组不可变