矩阵
本节目标
统一二维坐标、边界和原地状态，掌握矩阵遍历、变换与有序搜索。
矩阵题并不是“把一维数组多套一层循环”。真正的难点在于同时维护行、列两个坐标，以及区分哪些边界仍然有效。本节把常见矩阵题归入四个模型：原地标记、边界收缩、几何变换和有序排除。
识别信号
看到以下条件时，可以优先寻找矩阵专用结构：
- 某个位置的状态会影响整行或整列；
- 需要按顺时针、对角线或分层顺序访问所有元素；
- 要求不借助额外矩阵完成旋转、翻转或状态更新；
- 每行与每列都单调有序，需要利用二维顺序排除候选。
先明确坐标语义：统一用 row 表示行、col 表示列。写代码前确认行数、列数和合法区间，能避免大部分下标错误。
问题模型与核心不变量
四类母题各有一个核心不变量：
- 原地标记：用矩阵已有的行或列保存“稍后需要处理”的信息；
- 边界收缩：
top、bottom、left、right包围尚未访问的矩形； - 几何变换：把旋转拆成转置和翻转，每一步都保持明确的坐标映射；
- 有序排除：选择一个能单向排除整行或整列的角落开始搜索。
矩阵算法的正确性往往不在某一行代码，而在“这次更新边界后，剩余矩形是否仍然精确表示未处理区域”。
通用模板
四边收缩模板：
top = 0, bottom = rows - 1
left = 0, right = cols - 1
while top <= bottom and left <= right:
处理上边，top 后移
处理右边，right 前移
若仍有剩余行，处理下边，bottom 前移
若仍有剩余列，处理左边，left 后移
右上角阶梯搜索模板：
row = 0, col = cols - 1
while row < rows and col >= 0:
if matrix[row][col] == target: 找到
if matrix[row][col] > target: col 左移
else: row 下移
每一步都排除一整列或一整行，因此不会回头。
模板变体
- 原地标记可以借用首行首列，也可以用一个整数的不同取值编码旧状态与新状态。
- 顺时针遍历和逆时针遍历只改变四条边的访问顺序，边界不变量相同。
- 顺时针旋转可以写成“转置后反转每一行”，逆时针旋转则对应另一种翻转组合。
- 若只有整行有序而列无序，右上角阶梯搜索不再成立，应改用逐行二分或其他结构。
母题序列
以下题目按必学顺序学习：
先学习如何复用原矩阵保存标记，再练习边界收缩和坐标变换，最后利用行列单调性排除候选。
常见误区
- 在发现零时立即清空整行整列，破坏后续判断所需的原始信息。
- 螺旋遍历最后一圈时不检查剩余边界，重复访问单行或单列。
- 旋转图像只做转置或只做翻转，遗漏另一半坐标变换。
- 从左上角搜索行列有序矩阵，遇到大小关系时无法唯一决定移动方向。
- 默认矩阵一定非空，在访问
matrix[0]前没有处理空矩阵。
迁移方向
掌握本节后，可以继续处理：
- 矩阵中的连通块与路径搜索；
- 二维前缀和与矩形区域查询；
- 原地多状态更新，例如生命游戏；
- 分层遍历、对角线遍历和其他坐标映射问题。
迁移时先问：我是在维护未访问边界、复用已有存储，还是利用二维顺序排除候选？模型一旦明确，坐标更新就不再是零散技巧。