矩阵
01 / 共享的机制
矩阵不是一条线性序列,而是一片二维坐标空间 —— 每个格子由两个下标共同决定, 二者按某种方式组合在一起。关键在于找到正确的「走法」。 三个经典子模式:原地旋转(转置 + 行翻转)、螺旋遍历(四条边界向内收缩)、阶梯搜索(从某个角出发,该角上一方向单调递增另一方向单调递减)。
01 / 一句话本质
90° 顺时针旋转可以拆成转置 + 每行翻转 —— 两遍干净的原地扫描,二者的复合恰好就是旋转, 不需要额外网格。
题目原地把矩阵顺时针旋转 90°M3×3
3×3 方阵。先做转置,再逐行翻转,原地完成 90° 顺时针旋转。
步
0 / 11
阶段
输入
剩余交换
—
0 / 11
02 / 模式骨架
# 阶段 1 —— 转置:对 i < j 交换 m[i][j] 与 m[j][i]for i in 0..n-1:for j in i+1..n-1:m[i][j], m[j][i] ← m[j][i], m[i][j]# 阶段 2 —— 每行翻转for i in 0..n-1:for j in 0..n/2-1:m[i][j], m[i][n-1-j] ← m[i][n-1-j], m[i][j]# 复合 ≡ 90° 顺时针;时间 O(N²),额外空间 O(1)
03 / 什么时候用这个模式
"矩阵 / 图像旋转 90°"
最经典的用例 —— LC 48。不要再申请第二个网格:先
转置 再逐行翻转,数学上正好等于旋转。"转置矩阵"
LC 867 —— 单独的第一阶段。同样的双层循环,只是不再做翻转。 单独认出这个原语很关键,后面碰到才能即时识别。
"翻转 / 镜像"
逆时针 90° = 先翻转每行,再转置(等价于:转置 + 翻转每列)。 相同的两种原语,顺序或轴改一下 —— 选两遍都能原地完成的形式。
"分层旋转"
另一种 O(1) 额外空间的做法:把同心方框看作 4 元环来旋转(上 ← 左 ← 下 ← 右 ← 上)。 复杂度相同,但下标算式很脆。只有在必须单遍完成时再用。
04 / 常见坑
i.
转置时迭代整个方阵,而不是
i < j。转置把每一对元素交换一次。如果内层循环
j 从 0 跑到 n-1,每一对都会被交换两次,矩阵又回到原状。 一定要限制在 j > i(严格上三角)。ii.
把顺时针和逆时针弄混。
顺时针 = 转置 + 翻转每行。逆时针 = 转置 + 翻转每列(或:翻转每行 + 转置)。 很容易方向写反;用 2×2 的
[[1,2],[3,4]] 校验一下 —— 顺时针应得到 [[3,1],[4,2]]。iii.
非要单遍原地完成。
做得到(分层 / 四元环),但下标算式极易写错。两阶段才是最干净的:每一阶段都是一行交换循环, 复合即旋转。只在必须时使用单遍版本。
05 / 去 LeetCode 上练习
四道题。第一题是教科书 90° 旋转;后三题练相同原语(转置、行翻转), 也练习把网格操作看作多遍复合的思维。
— / 什么时候用哪个
原地旋转
题目要做的是网格本身的几何变换 —— 90° / 180° 旋转、转置、镜像时使用。 拆成两步(转置 + 行翻转)就能原地完成,不需要新的网格。
转置 + 翻转 · LC 48
螺旋遍历
需要按外圈顺序访问每个格子 —— 螺旋输出、螺旋填充、统计层数时使用。 维护四条边界,每走完一圈就把它们向内收缩。
四条边界 · LC 54 · LC 59
阶梯搜索
矩阵行列都单调且要查找一个值时使用。从一个「一方向递增、另一方向递减」的角出发, 每次比较都能淘汰整行或整列。
右上角出发 · LC 240 · O(N + M)