矩阵问题概述
矩阵（二维数组）是数组的进阶形态，其操作往往涉及行与列的联动。相比于普通一维数组，矩阵题更强调下标映射和原地修改，常见技巧包括：
- 原地标记：利用数组自身元素（如第一行、第一列）作为标记，避免额外空间。
- 分层模拟：按圈层（或边界）逐层处理，常用于螺旋遍历、旋转等。
- 转置 + 翻转：通过两次基本变换合成复杂旋转。
- 二分搜索或单调性剪枝：利用矩阵的排序特性快速查找。
LeetCode 热门 100 题中，有四道矩阵经典题覆盖了上述各类技巧：73. 矩阵置零（原地标记）、54. 螺旋矩阵（分层模拟）、48. 旋转图像（转置+翻转）、240. 搜索二维矩阵 II（单调性剪枝）。下面逐一拆解。
1. 矩阵置零（LeetCode 73）
题目：给定一个 m×n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。要求使用原地算法（空间复杂度 O(1)）。
暴力法：复制一个原矩阵，遍历原矩阵发现 0 就去复制矩阵中置零，最后复制回来，空间 O(mn)。
优化思路（原地标记）： 利用矩阵的第一行和第一列作为"标记位"，记录哪些行、列需要置零。但需提前记录第一行和第一列本身是否包含 0，以免被覆盖后丢失信息。
具体步骤：
- 检查第一行和第一列是否有 0，分别用
rowZero和colZero布尔值记录。 - 遍历矩阵（除第一行第一列外），若
matrix[i][j] == 0，则将matrix[i][0] = 0和matrix[0][j] = 0作为标记。 - 再次遍历（除第一行第一列外），若
matrix[i][0] == 0或matrix[0][j] == 0，则将matrix[i][j] = 0。 - 根据
rowZero和colZero决定是否将第一行、第一列置零。
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean rowZero = false, colZero = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) colZero = true;
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) rowZero = true;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (colZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
if (rowZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
}
复杂度：时间 O(mn)，空间 O(1)。
关键点：必须提前保存第一行第一列的状态，否则标记过程会污染原始信息；置零顺序先内后外，保证标记不被覆盖。
2. 螺旋矩阵（LeetCode 54）
题目：给定一个 m×n 矩阵，按顺时针螺旋顺序返回矩阵中的所有元素。
优化思路（分层模拟）：
定义四个边界：top、bottom、left、right，按顺序遍历上、右、下、左四条边，每遍历完一条边就收缩对应边界，直到边界交错。
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix.length == 0) return result;
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) result.add(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
left++;
}
}
return result;
}
复杂度：时间 O(mn)，空间 O(1)（除输出外）。
关键点：每遍历完一条边立即收缩对应边界，并在下边和左边遍历前检查边界是否仍然有效，避免重复添加。
3. 旋转图像（LeetCode 48）
题目：给定一个 n×n 的二维矩阵，将其顺时针旋转 90 度。要求原地旋转。
暴力法：创建新矩阵，按映射关系填入，空间 O(n²)。
优化思路（转置 + 水平翻转）： 顺时针旋转 90 度等价于先对矩阵进行转置（行变列），再对每一行进行水平翻转。这两步都可以原地完成。
public void rotate(int[][] matrix) {
int n = matrix.length;
// 转置
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 水平翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < n/2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n-1-j];
matrix[i][n-1-j] = temp;
}
}
}
复杂度：时间 O(n²)，空间 O(1)。
关键点：转置时内层循环从 i 开始避免交换两次；水平翻转每行只需遍历前一半。
4. 搜索二维矩阵 II（LeetCode 240）
题目：在一个 m×n 矩阵中搜索目标值，矩阵的每行从左到右升序，每列从上到下升序。要求时间复杂度 O(m+n)。
暴力法：遍历所有元素 O(mn)。
优化思路（Z 字形搜索）： 从矩阵的右上角（或左下角）开始。若当前值等于目标，返回 true；若当前值大于目标，则向左移动（列减 1），因为该列下方元素都更大，不可能包含目标；若当前值小于目标，则向下移动（行加 1），因为该行左边元素都更小。每一步排除一行或一列，直到越界。
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
}
复杂度：时间 O(m+n)，空间 O(1)。
关键点：利用矩阵的排序特性，每次比较都能排除一整行或一整列；起始点选右上角或左下角均可。
四题对比与启发
| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 | 特殊要求 |
|---|---|---|---|---|
| 矩阵置零 | 原地标记（第一行第一列作标记） | O(mn) | O(1) | 原地修改 |
| 螺旋矩阵 | 分层模拟（四边界收缩） | O(mn) | O(1) | 顺序输出 |
| 旋转图像 | 转置 + 水平翻转 | O(n²) | O(1) | 原地旋转 |
| 搜索二维矩阵 II | Z 字形剪枝（右上角开始） | O(m+n) | O(1) | 利用行列有序 |
共同本质：矩阵题的优化核心在于 “信息复用” 和 “空间节约”。置零题用第一行第一列作标记避免额外数组；螺旋题通过边界变量逐步收缩避免重复访问；旋转题通过两次基本变换合成复杂操作；搜索题则利用有序性进行单向移动。
不同侧重：
- 73：用矩阵自身存储辅助信息，前提是必须保留原始标志位。
- 54：注重边界控制和方向切换，属于纯模拟。
- 48：拆分变换步骤，利用转置和翻转的结合。
- 240：利用元素之间的偏序关系，每次排除一整行/列。
总结：矩阵模块的核心心法
矩阵题的核心在于"将二维操作转化为一维或常量操作"。无论是用一行/列作标记，还是按圈层分解，亦或是拆分为简单变换的组合，目的都是避免 O(n²) 的额外空间或冗余遍历。
解题时的思考路径：
- 若需要记录整行/整列的状态，考虑用第一行/列作标记（但注意保护原信息）。
- 若需要按顺序遍历所有元素，使用边界收缩法（螺旋）。
- 若需要旋转或镜像，分解为转置 + 翻转的组合。
- 若需要快速查找且矩阵具有有序性，利用其单调性进行单方向移动。
掌握这四道题，矩阵类问题的基础技法便已覆盖过半，遇到变形题（如螺旋矩阵 II、对角线遍历等）也能快速迁移。