算法面试突击手册 —— 矩阵/多维数组
一、概念与特点
大白话 + 类比
矩阵题 = 棋盘上的艺术
矩阵（二维数组）的题目不像链表/树有固定的数据结构，而是考你对”二维坐标”的感觉：
- 遍历类：螺旋走、蛇形走、对角线走——核心是控制行走的边界
- 变换类：旋转、翻转、转置——核心是找到坐标对应关系
- 标记类：原地标记 0 位——核心是借用第一行/列当”布告栏”
- 搜索类：行列有序——核心是从特殊位置（右上角）出发
- DP 降维类：二维最大矩形——核心是转化为一维经典问题
六大矩阵题型与核心技巧
| 类型 | 核心技巧 | 代表题 |
|---|---|---|
| 螺旋遍历 | 四边界 top/bottom/left/right 逐步收缩 | 54 |
| 原地置零 | 第一行 + 第一列做 O(1) 标记数组 | 73 |
| 旋转图像 | 转置 + 水平翻转（两步变换） | 48 |
| 行列有序搜索 | 从右上角出发 O(m+n) | 240 |
| 最大正方形 | DP：三邻居取最小+1 | 221 |
| 最大矩形 | 逐行转柱状图 + 单调栈 | 85 |
二、Hot 100 精讲题目
54. Spiral Matrix 螺旋矩阵
📌 按顺时针螺旋顺序返回矩阵所有元素。如
[[1,2,3],[4,5,6],[7,8,9]]→[1,2,3,6,9,8,7,4,5]
🔍 解题分析
核心思路（四边界收缩）
定义 top, bottom, left, right 四个边界，按”右 → 下 → 左 → 上”的顺序遍历。每走完一个方向，对应边界就往里收缩一格。终止条件：top > bottom 或 left > right。
类比：就像剥洋葱，一圈一圈从外往里剥。每剥完一圈，边界就往里缩一格。
为什么需要内层判断
在走”下边”和”左边”前，需要再次判断边界——因为走完”右边”后 top 已经下移了，可能已经超过 bottom（单行矩阵：[[1,2,3]]）。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 单行/单列 | 走完第一个方向后边界可能已越界，必须再次判断 |
| 方向顺序 | 必须是右→下→左→上，顺时针 |
| 边界收缩时机 | 走完一个方向立刻收缩对应边界 |
✅ 完整 Java 实现
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
// 四个边界
int top = 0; // 上边界（行）
int bottom = matrix.length - 1; // 下边界（行）
int left = 0; // 左边界（列）
int right = matrix[0].length - 1; // 右边界（列）
while (top <= bottom && left <= right) {
// 1. 左 → 右（沿上边界）
for (int j = left; j <= right; j++) {
result.add(matrix[top][j]);
}
top++; // 上边界下移——这一行走完了
// 2. 上 → 下（沿右边界）
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--; // 右边界左移——这一列走完了
// 3. 右 → 左（沿下边界）——需再次判断，防止单行重复遍历
if (top <= bottom) {
for (int j = right; j >= left; j--) {
result.add(matrix[bottom][j]);
}
bottom--; // 下边界上移
}
// 4. 下 → 上（沿左边界）——需再次判断，防止单列重复遍历
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++; // 左边界右移
}
}
return result;
}手算验证：[[1,2,3],[4,5,6],[7,8,9]]
| 轮次 | 遍历内容 | top/bottom/left/right 变化 |
|---|---|---|
| 1-右 | [1,2,3] | top:0→1 |
| 1-下 | [6,9] | right:2→1 |
| 1-左 | [8,7] | bottom:2→1 |
| 1-上 | [4] | left:0→1 |
| 2-右 | [5] | top:1→2 |
结果 [1,2,3,6,9,8,7,4,5] ✓
⏱ 复杂度分析
- 时间：O(mn) —— 每个元素访问恰好一次
- 空间：O(1) —— 不算返回列表
💡 记忆口诀
“top/bottom/left/right 四边界，右下左上轮流走，走完哪边缩哪边”
73. Set Matrix Zeroes 矩阵置零
📌 若
matrix[i][j] == 0，则第 i 行和第 j 列所有元素都置 0。必须原地操作。
🔍 解题分析
为什么不能用额外数组标记
最简单的想法是开两个 boolean[] 数组分别记录哪行哪列需要置零，但空间 O(m+n)。题目进阶要求 O(1) 空间。
O(1) 空间的核心技巧
把第一行和第一列本身当成标记数组（布告栏）！
- 先检查第一行和第一列自身是否含 0，用两个 boolean 记下来
- 遍历剩余矩阵（
matrix[1..][1..]），遇到 0 就在对应的第一行和第一列的格子上做标记 - 根据标记将对应行列置零（仍然只处理
[1..][1..]） - 最后根据第 1 步的两个 boolean 处理第一行和第一列
类比：把第一行和第一列当作”布告栏”。某个位置是 0，就在它对应的第一行（同列）和第一列（同行）的布告栏上各贴一个条。最后根据布告栏，把该清零的行列清掉。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| matrix[0][0] 的歧义 | 它既是第一行的标记又是第一列的标记，所以第一行和第一列需要单独的 boolean |
| 标记和清零的顺序 | 先标记，再清零非首行首列，最后处理首行首列 |
| 原地要求 | 不能用额外数组，但可以用第一行/列本身 |
✅ 完整 Java 实现
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// 第一步：记录第一行和第一列自身是否需要置零
boolean firstRowHasZero = false; // 第一行是否需要置零
boolean firstColHasZero = false; // 第一列是否需要置零
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) firstRowHasZero = true;
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) firstColHasZero = true;
}
// 第二步：用第一行和第一列做"布告栏"
// 如果 matrix[i][j] == 0，就在 matrix[i][0] 和 matrix[0][j] 标记
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0; // 第 i 行需要清零
matrix[0][j] = 0; // 第 j 列需要清零
}
}
}
// 第三步：根据布告栏置零（跳过第一行和第一列）
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 (firstRowHasZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColHasZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}⏱ 复杂度分析
- 时间：O(mn) —— 每个格子访问常数次
- 空间：O(1) —— 只用了两个 boolean 变量
💡 记忆口诀
“第一行第一列当布告栏贴条；先检查自身用 boolean 记，再遍历贴条，最后按条清零”
48. Rotate Image 旋转图像
📌 n×n 矩阵顺时针旋转 90°，必须原地操作。
🔍 解题分析
核心技巧：两步变换
顺时针旋转 90° = 转置（沿主对角线翻转）+ 每行水平翻转（左右反转）
原始 转置后 转置+每行翻转
1 2 3 1 4 7 7 4 1
4 5 6 → 2 5 8 → 8 5 2
7 8 9 3 6 9 9 6 3为什么这个方法正确：
- 坐标映射：
(i, j) → (j, i) → (j, n-1-i)恰好是顺时针 90° 的变换 - 分两步做每步都是原地操作
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 转置时 j 从 i+1 开始 | 只遍历对角线上半部分，否则会翻转两次回到原位 |
| 水平翻转时 j < n/2 | 只翻转一半，否则也是翻转两次 |
| n 为奇数时中间列 | 水平翻转 n/2 下取整，中间列不动 |
✅ 完整 Java 实现
public void rotate(int[][] matrix) {
int n = matrix.length;
// 第一步：转置 —— 沿主对角线 (i,j) ↔ (j,i)
for (int i = 0; i < n; i++) {
// 注意 j 从 i+1 开始，只处理上半三角
// 否则会翻转两次等于没动
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 第二步：每行水平翻转 —— (i,j) ↔ (i, n-1-j)
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;
}
}
}手算验证：[[1,2,3],[4,5,6],[7,8,9]]
转置后：[[1,4,7],[2,5,8],[3,6,9]]
每行翻转后：[[7,4,1],[8,5,2],[9,6,3]] ✓
⏱ 复杂度分析
- 时间：O(n²) —— 每个元素访问常数次
- 空间：O(1) —— 原地操作，仅用 temp 变量
💡 记忆口诀
“先沿对角线翻（转置），再每行左右翻——90 度就成了”
240. Search a 2D Matrix II 搜索二维矩阵 II
📌 矩阵每行升序、每列升序。搜索 target 是否存在。如
[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target=5→ true
🔍 解题分析
为什么从右上角出发
右上角是一行中最大的、一列中最小的。这个特殊位置给了我们二选一的方向：
- target > 当前值 → 排除这一行（往下走，值变大）
- target < 当前值 → 排除这一列（往左走，值变小）
每次比较都可以排除一整行或一整列，复杂度 O(m+n)。
为什么不能从左上角出发：左上角是一行最小、一列最小，如果 target 比它大，有两个方向可走（右、下），无法决定，退化为 DFS。
核心思路（步骤化）
- 从右上角
(0, n-1)出发 - 循环条件：
row < m && col >= 0 - 相等 → true；小于 → row++（找更大的）；大于 → col—（找更小的）
- 循环结束 → false
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 出发点选错 | 必须右上角或左下角，不能左上或右下 |
| 越界条件 | row 超过 m-1 或 col 小于 0 时停止 |
类比：你在右上角山顶。往左走是下坡（值变小），往下走是上坡（值变大）。目标值的方向决定了你该往哪走。
✅ 完整 Java 实现
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
// 从右上角出发
int row = 0, col = n - 1;
while (row < m && col >= 0) {
int cur = matrix[row][col];
if (cur == target) {
return true;
} else if (cur < target) {
// 当前值比 target 小 → 这一行左边都更小，排除整行
row++;
} else {
// 当前值比 target 大 → 这一列下面都更大，排除整列
col--;
}
}
return false; // 越界了还没找到
}手算验证：target = 5，从右上角 15 开始
| row | col | cur | 比较 | 操作 |
|---|---|---|---|---|
| 0 | 4 | 15 | 15 > 5 | col—（排除第 4 列） |
| 0 | 3 | 11 | 11 > 5 | col—（排除第 3 列） |
| 0 | 2 | 7 | 7 > 5 | col—（排除第 2 列） |
| 0 | 1 | 4 | 4 < 5 | row++（排除第 0 行） |
| 1 | 1 | 5 | 5 == 5 | ✓ true |
⏱ 复杂度分析
- 时间：O(m + n) —— 最多走 m 步向下 + n 步向左
- 空间：O(1)
💡 记忆口诀
“从右上角出发：小了向下，大了向左；每步排除一行或一列”
221. Maximal Square 最大正方形
📌 在 ‘0’ 和 ‘1’ 组成的矩阵中，找出只含 ‘1’ 的最大正方形，返回面积。如
[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]→ 4
🔍 解题分析
为什么用 DP
暴力法：枚举所有可能的正方形左上角和边长 O(mn × min(m,n))。DP 可以优化到 O(mn)。
状态定义：dp[i][j] = 以 (i, j) 为右下角的最大正方形的边长。
转移方程：
如果 matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1正方形要求四个角都是 1。(i,j) 是右下角时，边长受限于左、上、左上三个邻居能提供的最大边长。就像四面围墙，最矮的那面决定水池能装多深。
手算推理：dp[i-1][j]=2 意味着以 (i-1,j) 为右下角可以形成 2×2 的正方形；同理左上和左边。三者取最短板 +1。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| dp 数组多开一行一列 | 简化第一行和第一列的初始化，dp[i+1][j+1] 对应 matrix[i][j] |
| 返回面积不是边长 | 最终答案是 maxSide * maxSide |
| ’0’ 和 ‘1’ 是字符 | 比较时写成 matrix[i][j] == '1' 而不是 == 1 |
✅ 完整 Java 实现
public int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// dp[i][j] = 以 (i-1, j-1) 为右下角的最大正方形边长
// 多开一行一列简化首行首列处理
int[][] dp = new int[m + 1][n + 1];
int maxSide = 0; // 记录遇到的最大边长
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
// 三邻居取最小 + 1
// dp[i][j] 对应左上方，dp[i+1][j] 对应上方，dp[i][j+1] 对应左方
dp[i + 1][j + 1] = Math.min(
Math.min(dp[i][j], dp[i + 1][j]),
dp[i][j + 1]
) + 1;
maxSide = Math.max(maxSide, dp[i + 1][j + 1]);
}
// matrix[i][j] == '0' 时 dp[i+1][j+1] 保持 0（默认值）
}
}
// 返回面积 = 边长²
return maxSide * maxSide;
}手算验证：[[1,1],[1,1]]
| i,j | val | 左(i,j+1) | 上(i+1,j) | 左上(i,j) | min+1 | dp[i+1][j+1] |
|---|---|---|---|---|---|---|
| 0,0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0,1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1,0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1,1 | 1 | 1 | 1 | 1 | 2 | 2 |
maxSide=2，面积=4 ✓
⏱ 复杂度分析
- 时间：O(mn) —— 每个格子访问一次
- 空间：O(mn) —— 可优化至 O(n)（只用上一行和当前行的数据）
💡 记忆口诀
“三邻居取最短板 + 1 —— 正方形的边长受限于最弱的一面”
85. Maximal Rectangle 最大矩形
📌 在只含 ‘0’ 和 ‘1’ 的矩阵中，找出只含 ‘1’ 的最大矩形面积。如
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]→ 6
🔍 解题分析
核心技巧：转化为 84 题（柱状图中最大矩形）
把矩阵的每一行看作一个”地基”，从地基向上统计连续的 ‘1’ 的个数作为柱子高度。然后把当前行的 heights[] 数组输入 84 题的单调栈算法，计算最大矩形面积。遍历所有行，取最大值。
类比：从上往下把矩阵压成一条一条的柱状图。每一行生成一张柱状图（柱子 = 该列向上连续 ‘1’ 的数量），然后用 84 题的单调栈求出该柱状图的最大矩形。所有行的最大矩形中取最优。
核心思路（步骤化）
- 创建
heights[n]数组，初始全 0 - 逐行遍历矩阵：
- 对每列 j：如果
matrix[i][j] == '1'，heights[j]++（柱子向上生长）；否则heights[j] = 0（柱子断了） - 对当前 heights 数组调用 84 题的
largestRectangleArea(heights) - 更新全局最大面积
- 对每列 j：如果
- 返回全局最大面积
为什么遇到 0 要清零：柱子要求连续。如果一个位置是 0，从上面延续下来的柱子就断了，高度必须从 0 重新开始。
✅ 完整 Java 实现
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n]; // 每一列向上连续 '1' 的高度
int maxArea = 0;
// 逐行向下扫描，更新 heights 并求最大矩形
for (int i = 0; i < m; i++) {
// 更新当前行的柱状图高度
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
heights[j]++; // 连续 '1'，柱子长高
} else {
heights[j] = 0; // 遇到 '0'，柱子断了
}
}
// 对当前柱状图求最大矩形
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
// ====== 84 题：柱状图中最大矩形（单调栈解法） ======
private int largestRectangleArea(int[] heights) {
int n = heights.length;
// 两端加哨兵高度 0，简化边界处理
int[] h = new int[n + 2];
System.arraycopy(heights, 0, h, 1, n); // h[0]=0, h[n+1]=0
Deque<Integer> stack = new ArrayDeque<>(); // 单调递增栈，存下标
int maxArea = 0;
for (int i = 0; i < h.length; i++) {
// 当前高度 < 栈顶高度 → 栈顶的右边界出现了，弹出并计算面积
while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
int height = h[stack.pop()]; // 以这根柱子为高
int width = i - stack.peek() - 1; // 左右边界之间的距离
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}手算验证（简化版）：matrix = [["1","0","1"],["1","1","1"]]
| 行 | heights | 最大矩形 |
|---|---|---|
| 0 | [1, 0, 1] | 1 (面积 1) |
| 1 | [2, 1, 2] | 3 (面积 3，取第 0,1,2 列各高 1) |
maxArea = 3。验证：第 2 行的 3 个 ‘1’ 组成的矩形面积 = 1×3 = 3 ✓
⏱ 复杂度分析
- 时间：O(mn) —— 每行调用一次单调栈 O(n)，共 m 行
- 空间：O(n) —— heights 数组 + 栈
💡 记忆口诀
“逐行压扁变柱状图，每行用单调栈找最大矩形，全局取最大”
🔜 上一章：14-堆
📚 全系列完。回到 00-总目录 开始系统刷题！