LeetCode 1314：矩阵区域和 | 二维前缀和

LeetCode 1314矩阵区域和 | 二维前缀和引言矩阵区域和Matrix Block Sum是 LeetCode 第 1314 题难度为 Medium。题目要求计算矩阵中以每个元素为中心、K×K 子矩阵区域的元素和。这道题是二维前缀和的经典应用展示了如何将一维前缀和的思想推广到二维情况。二维前缀和是处理二维矩阵区间查询的强大工具。在图像处理、格子计算、统计问题等领域有广泛应用。本文将详细讲解二维前缀和的原理、实现和应用。问题分析题目描述给定一个矩阵 mat 和一个整数 K以每个位置 (r, c) 为中心计算以 (r, c) 为中心的 K×K 子矩阵的元素和。注意子矩阵的边界不能超出原矩阵。例如如果 mat [[1,2,3],[4,5,6],[7,8,9]]K 1那么以每个位置为中心的 1×1 子矩阵的元素和就是矩阵本身以 (0, 0) 为中心的 2×2 子矩阵的和为 124512。问题特点这道题的核心挑战是如何高效地计算大量子矩阵的和。如果对每个位置都遍历其 K×K 子矩阵的所有元素时间复杂度为 O(mnk²)对于大规模数据效率低下。二维前缀和可以将每个子矩阵的和计算优化到 O(1)总时间复杂度为 O(m*n)。这个优化类似于一维情况下使用前缀和将区间和查询从 O(n) 优化到 O(1)。二维前缀和原理定义给定矩阵 matrix其二维前缀和 prefix[i][j] 定义为以 (0, 0) 为左上角(i, j) 为右下角的矩形区域中所有元素的和。计算公式二维前缀和的计算公式为prefix[i][j] matrix[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1]这个公式基于容斥原理加上当前元素 matrix[i][j]加上上方矩形 prefix[i-1][j]包含 matrix[0:i, j]加上左方矩形 prefix[i][j-1]包含 matrix[i, 0:j]减去左上角矩形 prefix[i-1][j-1]被重复加了一次子矩阵和的计算给定前缀和数组 prefix可以 O(1) 计算任意子矩阵 [(r1, c1), (r2, c2)] 的和sum prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] prefix[r1-1][c1-1]问题解决构建前缀和def matrixBlockSum(mat, k): m, n len(mat), len(mat[0]) prefix [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): prefix[i][j] mat[i-1][j-1] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] result [[0] * n for _ in range(m)] for i in range(m): for j in range(n): r1, c1 max(0, i - k), max(0, j - k) r2, c2 min(m - 1, i k), min(n - 1, j k) result[i][j] (prefix[r21][c21] - prefix[r1][c21] - prefix[r21][c1] prefix[r1][c1]) return result注意前缀和数组比原矩阵大 1这样可以简化边界计算。计算子矩阵和时需要将索引加 1 以对应前缀和数组。复杂度分析时间复杂度构建前缀和O(mn)计算结果O(mn)总时间复杂度O(m*n)空间复杂度前缀和数组O(mn)结果数组O(mn)总空间复杂度O(m*n)代码实现Python 实现def matrixBlockSum(mat, k): m, n len(mat), len(mat[0]) prefix [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): prefix[i][j] mat[i-1][j-1] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] result [[0] * n for _ in range(m)] for i in range(m): for j in range(n): r1, c1 max(0, i - k), max(0, j - k) r2, c2 min(m - 1, i k), min(n - 1, j k) result[i][j] (prefix[r21][c21] - prefix[r1][c21] - prefix[r21][c1] prefix[r1][c1]) return resultJava 实现public int[][] matrixBlockSum(int[][] mat, int k) { int m mat.length; int n mat[0].length; int[][] prefix new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { prefix[i][j] mat[i - 1][j - 1] prefix[i - 1][j] prefix[i][j - 1] - prefix[i - 1][j - 1]; } } int[][] result new int[m][n]; for (int i 0; i m; i) { for (int j 0; j n; j) { int r1 Math.max(0, i - k); int c1 Math.max(0, j - k); int r2 Math.min(m - 1, i k); int c2 Math.min(n - 1, j k); result[i][j] prefix[r2 1][c2 1] - prefix[r1][c2 1] - prefix[r2 1][c1] prefix[r1][c1]; } } return result; }边界情况处理边界收缩由于子矩阵不能超出原矩阵边界需要将 r1、c1 向下收缩到不小于 0将 r2、c2 向上收缩到不超过 m-1、n-1。代码中使用了 max 和 min 函数来处理这种情况。K 很大当 K 很大时子矩阵可能覆盖整个矩阵边界收缩后结果就是整个矩阵的元素和。前缀和数组的处理方式确保了这种情况的正确性。空矩阵当矩阵为空时应该返回空结果。代码会正确处理因为 m 和 n 都为 0。测试用例def test_matrix_block_sum(): mat1 [[1, 2, 3], [4, 5, 6], [7, 8, 9]] assert matrixBlockSum(mat1, 1) [[12, 21, 16], [27, 45, 33], [19, 33, 24]] mat2 [[1]] assert matrixBlockSum(mat2, 0) [[1]] mat3 [[1, 2], [3, 4]] assert matrixBlockSum(mat3, 0) [[1, 2], [3, 4]] print(所有测试用例通过)扩展问题可变查询的矩阵区域和如果需要支持多次不同 K 值的查询可以预先构建二维前缀和然后对每个查询使用 O(1) 时间计算。动态更新的矩阵如果矩阵需要支持更新操作如修改某个元素可以使用二维树状数组Binary Indexed Tree或二维线段树来支持 O(log m * log n) 的更新和查询。更大维度将二维前缀和推广到更高维度是直接的。三维前缀和用于计算长方体的元素和公式为prefix[i][j][k] matrix[i][j][k] prefix[i-1][j][k] prefix[i][j-1][k] prefix[i][j][k-1] - ...实际应用场景二维前缀和在现实中有很多应用。在图像处理中可以用来计算某个区域的像素平均值或总和。在地理信息系统GIS中可以用来计算某个矩形区域的人口、面积等统计信息。在游戏开发中可以用来计算格子游戏的区域分数。二维前缀和也是其他二维算法问题的基础如二维最大子矩阵和问题、矩阵中的路径问题等。总结矩阵区域和问题展示了二维前缀和在处理矩阵区间查询中的应用。通过使用二维前缀和我们可以将每个子矩阵和的查询从 O(k²) 优化到 O(1)总时间复杂度从 O(mnk²) 优化到 O(m*n)。二维前缀和的核心是容斥原理将一个大矩形分解为四个子矩形的和。希望通过本文的讲解读者能够掌握二维前缀和的原理和应用并将其推广到更高维度或其他类似问题的解决中。