当前位置：首页 > news >正文

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

news 2026/5/24 0:59:09

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 子矩阵的和为 1+2+4+5=12。

问题特点

这道题的核心挑战是如何高效地计算大量子矩阵的和。如果对每个位置都遍历其 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[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][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[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]) return result

Java 实现

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("所有测试用例通过！")