LeetCode 1314中等图 · 网格
矩阵区域和 图解题解
这道题到底在问什么
把定义抠清楚:answer[i][j] 收集的是所有满足 i-k ≤ r ≤ i+k 且 j-k ≤ c ≤ j+k 的格子 mat[r][c] 之和。也就是以 (i,j) 为中心、边长 2k+1 的正方形窗口,但窗口超出矩阵的部分要剪掉。k=1 时窗口是 3 乘 3,中心在角落就只剩 2 乘 2,在边上就剩 2 乘 3。最朴素的做法是对每个 (i,j) 都去把窗口里的格子一个个加起来,那是四重循环;我们要用二维前缀和把每次求和压成几步加减。
- 输入
- mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
- 输出
- answer[1][1] = 整个矩阵的和 = 45
- 输入
- 同上, answer[0][0]
- 输出
- 左上角窗口被剪成 2 乘 2:1+2+4+5 = 12
- 输入
- 同上, answer[2][2]
- 输出
- 右下角窗口剪成 2 乘 2:5+6+8+9 = 28
最优解：一步一步想明白
- 3记住两句:建表是「上加左减左上再加当前」;查矩形和是「大块减上条减左条加左上块」。窗口边界先用 max、min 钳进矩阵,再套查询公式。
- 4这是要处理的 3 乘 3 矩阵,行号 i 从上往下 0 到 2,列号 j 从左往右 0 到 2,数值就是 1 到 9 顺着排。k 等于 1,意味着每个中心格要把自己和周围一圈共九个格子加起来,挨着边或角的中心则只能加到落在矩阵里的那几格。先把这张原图记在心里,接下来去搭前缀和表。
- 5前缀和表 s 比原矩阵多一行一列,这里是 4 乘 4。最上面那一行和最左边那一列全部预填 0,它们是哨兵,代表「一个格子都还没框进来」时的和。有了这圈零,后面递推到第一行第一列时就不用单独写边界判断。中间打点的格子是待会儿要逐个填的真实前缀和。
- 6填 s[1][1],它代表原矩阵左上角到第 0 行第 0 列这块的总和。把上面一块 0 和左边一块 0 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 1,得到 1。
- 7填 s[1][2],它代表原矩阵左上角到第 0 行第 1 列这块的总和。把上面一块 0 和左边一块 1 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 2,得到 3。
- 8填 s[1][3],它代表原矩阵左上角到第 0 行第 2 列这块的总和。把上面一块 0 和左边一块 3 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 3,得到 6。
- 9填 s[2][1],它代表原矩阵左上角到第 1 行第 0 列这块的总和。把上面一块 1 和左边一块 0 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 4,得到 5。
- 10填 s[2][2],它代表原矩阵左上角到第 1 行第 1 列这块的总和。把上面一块 3 和左边一块 5 加起来,这俩在左上角那一小块 1 上重复算了一次,减掉它,再补上当前格自己的 5,得到 12。
- 11填 s[2][3],它代表原矩阵左上角到第 1 行第 2 列这块的总和。把上面一块 6 和左边一块 12 加起来,这俩在左上角那一小块 3 上重复算了一次,减掉它,再补上当前格自己的 6,得到 21。
- 12填 s[3][1],它代表原矩阵左上角到第 2 行第 0 列这块的总和。把上面一块 5 和左边一块 0 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 7,得到 12。
- 13填 s[3][2],它代表原矩阵左上角到第 2 行第 1 列这块的总和。把上面一块 12 和左边一块 12 加起来,这俩在左上角那一小块 5 上重复算了一次,减掉它,再补上当前格自己的 8,得到 27。
- 14填 s[3][3],它代表原矩阵左上角到第 2 行第 2 列这块的总和。把上面一块 21 和左边一块 27 加起来,这俩在左上角那一小块 12 上重复算了一次,减掉它,再补上当前格自己的 9,得到 45。
- 15九个真实前缀和全部填好。最右下角 s[3][3] 等于 45,刚好是整个矩阵九个数的总和,可以拿来自检。现在这张表的威力在于:原矩阵里任意一个矩形区域的和,都能用它四个角的值一加减算出来,不用再去逐格累加。下面就用它来回答每个 answer[i][j]。
- 16现在算中心在 (0,0) 的窗口。理论窗口是行 -1 到 1、列 -1 到 1。窗口探出了矩阵,被钳成矩形 行 0..1、列 0..1。点亮的这几格 1 + 2 + 4 + 5 就是要相加的区域,直接加是 12,接下来用前缀表一步算出同样的结果。
- 17钳好的矩形是行 0 到 1、列 0 到 1。套区域查询公式:大块到右下角 s[2][2] 是 12,减掉上面那条 s[0][2] = 0,再减掉左边那条 s[2][0] = 0,左上角那块被多减了一次要补回来 s[0][0] = 0。12 减 0 减 0 加 0 等于 12,和刚才直接相加完全一致。
- 18现在算中心在 (0,1) 的窗口。理论窗口是行 -1 到 1、列 0 到 2。窗口探出了矩阵,被钳成矩形 行 0..1、列 0..2。点亮的这几格 1 + 2 + 3 + 4 + 5 + 6 就是要相加的区域,直接加是 21,接下来用前缀表一步算出同样的结果。
- 19钳好的矩形是行 0 到 1、列 0 到 2。套区域查询公式:大块到右下角 s[2][3] 是 21,减掉上面那条 s[0][3] = 0,再减掉左边那条 s[2][0] = 0,左上角那块被多减了一次要补回来 s[0][0] = 0。21 减 0 减 0 加 0 等于 21,和刚才直接相加完全一致。
- 20现在算中心在 (1,1) 的窗口。理论窗口是行 0 到 2、列 0 到 2。窗口正好落在矩阵内,不需要钳,行 0..2、列 0..2。点亮的这几格 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 就是要相加的区域,直接加是 45,接下来用前缀表一步算出同样的结果。
- 21钳好的矩形是行 0 到 2、列 0 到 2。套区域查询公式:大块到右下角 s[3][3] 是 45,减掉上面那条 s[0][3] = 0,再减掉左边那条 s[3][0] = 0,左上角那块被多减了一次要补回来 s[0][0] = 0。45 减 0 减 0 加 0 等于 45,和刚才直接相加完全一致。
- 22现在算中心在 (1,2) 的窗口。理论窗口是行 0 到 2、列 1 到 3。窗口探出了矩阵,被钳成矩形 行 0..2、列 1..2。点亮的这几格 2 + 3 + 5 + 6 + 8 + 9 就是要相加的区域,直接加是 33,接下来用前缀表一步算出同样的结果。
- 23钳好的矩形是行 0 到 2、列 1 到 2。套区域查询公式:大块到右下角 s[3][3] 是 45,减掉上面那条 s[0][3] = 0,再减掉左边那条 s[3][1] = 12,左上角那块被多减了一次要补回来 s[0][1] = 0。45 减 0 减 12 加 0 等于 33,和刚才直接相加完全一致。
- 24现在算中心在 (2,2) 的窗口。理论窗口是行 1 到 3、列 1 到 3。窗口探出了矩阵,被钳成矩形 行 1..2、列 1..2。点亮的这几格 5 + 6 + 8 + 9 就是要相加的区域,直接加是 28,接下来用前缀表一步算出同样的结果。
- 25钳好的矩形是行 1 到 2、列 1 到 2。套区域查询公式:大块到右下角 s[3][3] 是 45,减掉上面那条 s[1][3] = 6,再减掉左边那条 s[3][1] = 12,左上角那块被多减了一次要补回来 s[1][1] = 1。45 减 6 减 12 加 1 等于 28,和刚才直接相加完全一致。
- 26把九个 answer 都按同样两步算出来,就是这张结果矩阵。正中 answer[1][1] 的窗口覆盖整张矩阵,值是 45;四个角因为窗口被剪成 2 乘 2,值最小;四条边上是 2 乘 3。每一格都只花常数步,这就是二维前缀和的好处。
⚠️ 容易写错的地方
✗ 错：前缀表只开和原矩阵一样大,没多那一圈零
✓ 对：开 (m+1)×(n+1),第 0 行第 0 列留 0 当哨兵
有了哨兵,递推到第一行第一列时 s[i][j+1] 等项天然取到 0,不必为边界单独写 if;查询时 x1、y1 也可能取到 0 这一圈,正好对应「没有上条 / 左条」
✗ 错：窗口边界忘了钳,直接用 i-k 或 i+k 去查
✓ 对：x1=max(i-k,0)、y1=max(j-k,0)、x2=min(m-1,i+k)、y2=min(n-1,j+k)
中心在角或边上时,i-k 会变负、i+k 会越过末行,不钳就会下标越界或把矩阵外的虚无格子算进来,答案就错了
✗ 错：区域查询公式四个角的下标或正负号记混
✓ 对：s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]
大块用右下角的 x2+1、y2+1;减去的上条、左条用 x1 或 y1;左上块被两条各减了一次,要加一次补回来。下标都带着那个 +1 偏移,别和原矩阵坐标混用
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
m, n = len(mat), len(mat[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(mat, 1):
for j, x in enumerate(row, 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
ans = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
x1, y1 = max(i - k, 0), max(j - k, 0)
x2, y2 = min(m - 1, i + k), min(n - 1, j + k)
ans[i][j] = (
s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1]
)
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> s(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
}
}
vector<vector<int>> ans(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x1 = max(i - k, 0);
int y1 = max(j - k, 0);
int x2 = min(m - 1, i + k);
int y2 = min(n - 1, j + k);
ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] s = new int[m + 1][n + 1];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
}
}
int[][] ans = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x1 = Math.max(i - k, 0);
int y1 = Math.max(j - k, 0);
int x2 = Math.min(m - 1, i + k);
int y2 = Math.min(n - 1, j + k);
ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
}
}
return ans;
}
}复杂度
时间
O(m·n)
建前缀表扫一遍全矩阵是 O(m·n);算答案再扫一遍全矩阵,每个 answer[i][j] 靠前缀表只做四次加减、常数时间。两段都是线性,合起来 O(m·n)。比逐格累加窗口的 O(m·n·k²) 快得多
空间
O(m·n)
按峰值算:前缀和表 s 是 (m+1)×(n+1),和原矩阵同量级,平方级。输出矩阵 answer 也是 m×n 但通常算进结果不计;没有递归,不额外吃栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 矩阵区域和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
二维前缀和的建表递推为什么是「上加左减左上再加当前」?+
s[i+1][j+1] 要的是左上角到 (i,j) 这个大矩形的和。上面那块 s[i][j+1] 盖住了前 i 行,左边那块 s[i+1][j] 盖住了前 j 列,这两块在「前 i 行且前 j 列」那个左上小矩形 s[i][j] 上重叠了,加两块就把它算了两遍,所以要减掉一个 s[i][j],最后补上当前格 mat[i][j]。这就是容斥:两块相加、减去重叠、补上新增。
查询任意矩形和的公式怎么来的?+
同样是容斥。要 (x1,y1) 到 (x2,y2) 这块矩形和,拿到右下角的大前缀块 s[x2+1][y2+1],它多含了上方一条和左方一条;减掉上条 s[x1][y2+1]、减掉左条 s[x2+1][y1],可左上角那个小块被这两条各覆盖了一次、被减了两遍,所以要加回一个 s[x1][y1]。四个角一加减就把目标矩形单独抠出来。
不用前缀和,直接对每个窗口累加行不行?复杂度差多少?+
行,但慢。每个 answer[i][j] 的窗口最多 (2k+1)² 个格子,对全部 m·n 个中心都逐格加,是 O(m·n·k²)。k 大时很贵。前缀和把「区域求和」从 O(k²) 降到 O(1),总复杂度压到 O(m·n),和 k 无关。这正是前缀和的典型用途:一次预处理,之后每次区间或区域查询都是常数时间。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 矩阵区域和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。