矩阵
01 / 共享的机制
矩阵不是一条线性序列,而是一片二维坐标空间 —— 每个格子由两个下标共同决定, 二者按某种方式组合在一起。关键在于找到正确的「走法」。 三个经典子模式:原地旋转(转置 + 行翻转)、螺旋遍历(四条边界向内收缩)、阶梯搜索(从某个角出发,该角上一方向单调递增另一方向单调递减)。
01 / 一句话本质
维护四条边界 —— 上、右、下、左 —— 沿着它们围成的矩形外圈走。 每走完一条边,就把对应边界向内收缩一格,如此循环,直到边界交叉。 矩阵被一层层地剥开,直到为空。
题目按螺旋顺序返回 M 的所有元素M1 2 3 ; 4 5 6 ; 7 8 9
网格 3 × 3。初始边界 top=0, bottom=2, left=0, right=2。沿外圈走、收缩、再走。
步
0 / 15
当前
—
已访问
0 / 9
0 / 15
02 / 模式骨架
# 用四条边界围住未访问的矩形top ← 0; bottom ← R-1left ← 0; right ← C-1while top ≤ bottom and left ≤ right:# 1) 沿 top 行从左到右for c in left..right: visit(top, c)top ← top + 1# 2) 沿 right 列从上到下for r in top..bottom: visit(r, right)right ← right − 1if top ≤ bottom:# 3) 沿 bottom 行从右到左for c in right..left: visit(bottom, c)bottom ← bottom − 1if left ≤ right:# 4) 沿 left 列从下到上for r in bottom..top: visit(r, left)left ← left + 1
03 / 什么时候用这个模式
"螺旋顺序遍历"
LC 54。最经典的用法 —— 按螺旋顺序输出每个格子。四条边界 + 四个方向 + 走完即收缩,
O(R · C) 时间,每个格子恰好访问一次。"按螺旋顺序填充矩阵"
LC 59。同样的走法,反过来用 —— 不再是读取,而是依次写入
1, 2, 3, …, n²。 边界框架完全一样,只是访问步从读变成写。"按层旋转 / 按层处理"
凡是能自然分解为同心圆环的问题 —— 每层原地旋转、按层做图像滤波、按层统计边长。 四边界框架就是「一层的迭代」,外面再套一个层数循环就够了。
"矩阵外圈相关问题"
题目关注矩形(或子矩形)边界上的格子时,螺旋走法一次性把它们都遍历完。 边界求和、环上查询、螺旋坐标谜题(LC 885、LC 2326)都用得上。
04 / 常见坑
i.
跳过第
3、4 趟前的条件检查。只剩一行或一列时,第三趟(沿 bottom 从右到左)会重新访问第一趟刚走过的那一行; 第四趟同理会重复一列。一定要用
top ≤ bottom 守住第三趟、 用 left ≤ right 守住第四趟。漏检之后,非正方形输入会输出重复元素。ii.
边界更新差一。
每条边界都在对应趟走完后移动 —— L→R 走完才
top++, T→B 走完才 right−−,依此类推。把 top++ 放错位置(走前 / 错方向), 就会把矩形挤扁,要么漏一行,要么重一行。iii.
写四段几乎重复的下标循环,而不是一个走位指针。
更清爽的写法:维护
(r, c) 加方向下标 d ∈ {0,1,2,3}, 配合 dr/dc 数组。走一步,如果会越过当前边界,就 d ← (d + 1) % 4并收缩刚刚离开的那条边界。一个循环、一种终止条件 —— 出错点比四段几近重复的 for 少得多。05 / 去 LeetCode 上练习
四道题练习螺旋走法。前两题是直接用法 —— 读 vs. 写;后两题把走法推广到任意起点和链表输出。
— / 什么时候用哪个
原地旋转
题目要做的是网格本身的几何变换 —— 90° / 180° 旋转、转置、镜像时使用。 拆成两步(转置 + 行翻转)就能原地完成,不需要新的网格。
转置 + 翻转 · LC 48
螺旋遍历
需要按外圈顺序访问每个格子 —— 螺旋输出、螺旋填充、统计层数时使用。 维护四条边界,每走完一圈就把它们向内收缩。
四条边界 · LC 54 · LC 59
阶梯搜索
矩阵行列都单调且要查找一个值时使用。从一个「一方向递增、另一方向递减」的角出发, 每次比较都能淘汰整行或整列。
右上角出发 · LC 240 · O(N + M)