聊到hot100很多人第一反应是链表、二叉树、动态规划矩阵题往往被当成“简单题”一笔带过。真到面试和笔试的时候矩阵题反而是翻车重灾区——Java选手写二维数组默认值、边界条件、方向控制任何一个环节掉链子整道题就崩了。这篇笔记是我自己刷hot100矩阵题的完整总结把螺旋矩阵、旋转图像、矩阵置零、搜索二维矩阵、岛屿数量、最大正方形、单词搜索这些高频题全部串起来讲清楚每类题的解题套路、Java写法要点和容易踩的坑。正在准备面试的朋友可以直接拿来当专题复习资料刚入门算法、想打牢二维数组基本功的Java开发者也能从里面找到可复现的代码模板。1. 先给矩阵题画个像hot100到底在考什么1.1 矩阵的本质是一张二维数组但考的不只是数组矩阵在Java里就是int[][] matrix本质是数组的数组或者说是一个“行优先存储”的二维结构。很多人觉得矩阵题简单因为语法上不就是两个for循环嵌套吗但真做起来就会发现矩阵题考的其实是四件基本功索引定位、行列遍历、边界判断、空间换时间。这四件事单拎出来都不难组合在一起就容易乱。我见过很多朋友刷矩阵题第一反应就是暴力枚举——把所有格子遍历一遍能过就算赢。但面试官真正想看的是你对“状态”和“边界”的理解。比如螺旋矩阵要用四条边界收缩转置要只遍历一半搜索二维矩阵II要从右上角走迷宫这些都不是暴力枚举能解决的。矩阵题不考矩阵论里那种分块矩阵求逆、特征值分解的数学推导考的就是二维数组的操作能力以及你在复杂度压力下能不能写出干净的代码。另外矩阵题特别适合用来考察代码风格。循环变量的命名、边界条件的处理、是否随手防御空数组这些小细节在面试官眼里都是信号。我自己的体会是把hot100里的矩阵题刷透比盲目刷几百道随机题有用得多因为它们的解题套路高度可复用一个模板能解决一大片问题。1.2 hot100矩阵题分类模拟、搜索、DFS/BFS、DP我刷完hot100里所有矩阵相关题目之后把它们分成了四大类。这个分类不是为了好看而是因为每一类的思维模式完全不同类型代表题目核心考点难度模拟与变换螺旋矩阵、旋转图像边界收缩、转置翻转中等原地标记矩阵置零空间复杂度优化、标记位复用中等搜索类搜索二维矩阵、搜索二维矩阵II一维化二分、右上角走位中等DFS/BFS与DP岛屿数量、单词搜索、最大正方形、最小路径和Flood Fill、回溯剪枝、状态转移中等到困难为什么要把分类讲清楚因为同一张矩阵考的思维模式完全不同。模拟题考的是“你能不能把转圈圈的过程描述清楚”搜索题考的是“你能不能利用有序性排除无效区间”DFS/BFS考的是“你能不能对连通区域做标记”DP题考的是“你能不能从小问题推到大问题”。分类刷的好处是你能在短时间内建立题感。比如看到“矩阵连通区域”就想到Flood Fill看到“矩阵有序”就想到二分或右上角走位看到“矩阵最值”就想到DP。这种条件反射只有分类刷才能练出来。下面我按这个分类把每道题的核心思路和Java写法逐一拆开讲。2. 模拟与变换把转圈圈和翻面写成代码2.1 螺旋矩阵四边界收缩法螺旋矩阵LeetCode 54是模拟题里的典型代表。题目要求你从外到内、顺时针遍历整个矩阵。很多人第一次写会陷入“手动模拟每个方向”的陷阱写出一大堆if-else最后边界条件一多就崩。我推荐的做法是维护四个边界变量top、bottom、left、right。每走完一圈四个边界各自向内收缩一格直到边界交叉为止。核心代码如下public ListInteger spiralOrder(int[][] matrix) { ListInteger result new ArrayList(); if (matrix null || matrix.length 0 || matrix[0].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]); } // 从上到下遍历当前右列 for (int i top 1; i bottom; i) { result.add(matrix[i][right]); } // 从右到左遍历当前底行防止单行重叠 if (top bottom) { for (int j right - 1; j left; j--) { result.add(matrix[bottom][j]); } } // 从下到上遍历当前左列防止单列重叠 if (left right) { for (int i bottom - 1; i top; i--) { result.add(matrix[i][left]); } } top; bottom--; left; right--; } return result; }这个解法的关键在于那两个if判断。不加的话当矩阵只剩一行或只剩一列时底行遍历或左列遍历会把已经输出过的元素再输出一遍。我第一遍写的时候就是漏了top bottom这个条件结果单行矩阵直接给我输出了一串重复元素。后来我把这个场景记死遍历底行和左列之前必须确认当前矩阵不是单行或单列。复杂度和直觉也一致每个元素恰好被访问一次时间O(mn)空间O(1)不考虑结果集。你可以把整个过程想象成剥洋葱一圈一圈往里剥直到剥完。2.2 旋转图像先转置再翻转别硬转旋转图像LeetCode 48要求顺时针旋转90度而且必须在原地完成。我第一次做这道题的时候试图用四元素循环交换硬转结果索引写对了三次写错了一次debug了一个小时才反应过来——这种解法太容易错了四个坐标的映射关系极其反直觉。后来我换了个思路顺时针旋转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转置之后每一行再反转结果正好是顺时针旋转90度。这个解法的优势非常明显两个步骤各自简单转置只涉及matrix[i][j]与matrix[j][i]交换反转就是标准的双指针或者直接循环交换每一步都好验证。Java代码如下public void rotate(int[][] matrix) { int n matrix.length; // 第一步沿主对角线转置只遍历上三角 for (int i 0; i n; i) { for (int j i 1; 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; } } }这里有个细节我要特别强调转置的二层循环j必须从i 1开始。如果从0开始等于每个元素交换两次转了个寂寞。我第一次写就是忘了这个结果矩阵原地不动还以为是翻转出了问题。同理逆时针旋转90度就是先转置再逐行上下翻转。这个思路一旦记住以后面试遇到旋转矩阵的变形题直接套“转置翻转”的组合就行。空间复杂度O(1)完美满足原地要求。2.3 模拟题实操心得方向数组真香模拟类的矩阵题除了四边界收缩和转置翻转还有一种是“方向”驱动的。比如螺旋矩阵也可以写成“方向数组碰撞换向”的版本维护一个dirs方向数组每一步都判断下一个格子是否越界或者已经被访问过是就换方向。方向数组在Java里写起来非常统一int[][] dirs {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};这个数组表示右、下、左、上四个方向。之后再配一个visited布尔数组或者直接在原数组上标记特殊值。为什么方向数组好用因为它把“方向”这个状态从硬编码的if-else里解放出来了。你只需要维护一个directionIndex每次走不通就(directionIndex 1) % 4换方向代码结构非常清晰。我自己的习惯是模拟题先想清楚状态变量是什么再写代码。螺旋矩阵的状态变量是四条边界旋转图像的状态变量是“转置翻转”两步操作边界驱动的模拟题状态变量就是坐标和方向索引。把状态想清楚了代码自然就写出来了。另外Java里处理矩阵时有一些常用的小工具比如Arrays.fill可以快速填充一维数组System.arraycopy可以拷贝数组行这些在笔试时能省不少时间。虽然面试一般不禁止用库函数但你要能说清楚这些方法的复杂度否则面试官会追问。3. 搜索和标记二维世界的二分与原地改造3.1 搜索二维矩阵先定位行再定位列也可以直接一维化搜索二维矩阵LeetCode 74的特点是矩阵的每一行递增并且下一行的第一个元素大于上一行的最后一个元素。这意味着整张矩阵从行优先的角度看就是一条排好序的一维数组。最直接的思路是先二分定位行再二分定位列时间复杂度O(log m log n)。但还有一个更骚的写法直接把这个逻辑上的一维数组做一次二分。关键是把一位下标mid映射回二维坐标int row mid / n; int col mid % n;这里n是列数。为什么要除以列数而不是行数因为矩阵是行优先存储的第mid个元素在第mid / n行、第mid % n列。这个映射是99%的人第一次写都会搞错的地方我见过有人除以m结果直接越界。完整代码如下public boolean searchMatrix(int[][] matrix, int target) { int m matrix.length; int n matrix[0].length; int left 0, right m * n - 1; while (left right) { int mid (left right) 1; int value matrix[mid / n][mid % n]; if (value target) { return true; } else if (value target) { left mid 1; } else { right mid - 1; } } return false; }这个解法的时间复杂度是O(log(mn))。面试的时候如果你能先说“矩阵满足全局有序所以可以一维化二分”再写出这段代码会是一个很加分的表现。因为大多数人只会想到“两次二分”一维化二分说明你抓住了“行优先存储”这个本质。3.2 搜索二维矩阵II从右上角走出来的二分思维搜索二维矩阵IILeetCode 240比上一题难一点矩阵只保证每行递增、每列递增但不存在“下一行第一个元素大于上一行最后一个元素”这样的全局有序。所以不能一维化二分。但这道题有一个经典解法的思路非常巧妙。你有没有用过单片机矩阵键盘它的行列扫描是不断地拉低一行、读一列从而定位按键。而这道题的最佳解法是从矩阵的右上角开始“走”public boolean searchMatrix(int[][] matrix, int target) { int m matrix.length; int 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) { row; } else { col--; } } return false; }为什么要从右上角出发因为右上角这个位置很特殊它是当前行的最大值同时也是当前列的最小值。如果当前值小于target说明这一行最大的数都比target小整行都可以排除所以向下移动一行如果当前值大于target说明这一列最小的数都比target大整列都可以排除所以向左移动一列。每一步都能排除一整行或一整列最多走mn步就能结束时间复杂度O(mn)。这个思路我愿称之为“走迷宫式搜索”它不需要二分查找但本质上依然是在利用有序性排除无效区间。面试中如果面试官让你优化你甚至可以说还能用“对每一行做二分”不过那是O(m log n)不如右上角走法来得优雅。记住面对行、列各自递增的矩阵优先想右上角或左下角。3.3 矩阵置零用第一行第一列当标记位矩阵置零LeetCode 73的题意是如果某个元素是0就把它所在的行和列全部置为0。最朴素的解法是开两个布尔数组分别记录哪些行、哪些列需要置零空间O(mn)。但题目有进阶要求能不能用O(1)空间答案是肯定的核心思想是复用矩阵的第一行和第一列作为标记数组。具体分三步第一步单独记录第一行和第一列原本是否有0。这一步非常重要因为后续我们会在第一行和第一列上做标记如果不提前记录原始信息就会被覆盖。boolean firstRowZero false; boolean firstColZero false; for (int j 0; j n; j) { if (matrix[0][j] 0) { firstRowZero true; break; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { firstColZero true; break; } }第二步遍历剩余区域遇到0就把对应的“行标记”和“列标记”落在第一行和第一列上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 (firstRowZero) { for (int j 0; j n; j) matrix[0][j] 0; } if (firstColZero) { for (int i 0; i m; i) matrix[i][0] 0; }这个解法的坑点非常隐蔽如果你一开始没有记录第一行第一列的状态而是直接用它们做标记那么当原来的matrix[0][0] 0或者第一行本身有0时你的标记信息就被污染了。我自己就吃过这个亏写出来运行结果全错最后单步调试才发现是标记行被提前置零了。这道题是典型的“原地算法”核心思路就是复用已有空间。面试时能写出O(1)空间解法会让面试官觉得你对空间复杂度有真实的敏感度。顺便提一句类似的“复用已有空间”思想在别的题目里也很常见比如用原数组标记元素是否出现等都是一脉相承的。4. DFS、BFS与动态规划矩阵题的进阶玩法4.1 岛屿数量Flood Fill模板一次会写到处能用岛屿数量LeetCode 200是矩阵题里最经典的DFS题目。给定一个char[][]矩阵1表示陆地0表示水连在一起的陆地算一个岛问总共有几个岛。解法的核心是Flood Fill洪泛填充遍历每一个格子遇到陆地就计数加一然后用DFS或BFS把整块陆地区域全部“淹没”标记为已访问避免重复计数。DFS版本写起来最简洁public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int count 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int i, int j) { if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] ! 1) { return; } grid[i][j] 0; dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); }这里我直接把访问过的陆地改成0也就是“淹没”省掉了一个visited二维数组的空间。为什么可以这么做因为题目不要求还原现场我们只需要统计数量改掉原数组不会影响结果。这在面试里是可以说的如果不允许修改原数组再额外开visited数组否则原地标记优先。BFS版本用队列也行逻辑差不多只是把递归换成迭代面试时可以看情况展示。这套Flood Fill模板掌握之后很多题都能直接套被围绕的区域、岛屿最大面积、太平洋大西洋水流问题这些hot100里的题本质都是同一个套路。学习算法的乐趣就在这种“一道题顶十道题”的复利效应。4.2 单词搜索回溯剪枝的实战套路单词搜索LeetCode 79是矩阵题里少有的“回溯”题。题目要求你在矩阵中找一条路径使得路径上的字符按顺序组成给定的单词每个格子只能走一次不能重复。解法框架是DFS 回溯。从每个格子出发如果当前字符匹配就继续向四个方向搜索如果某个方向走不通就回退并且把访问标记还原。核心代码如下public boolean exist(char[][] board, String word) { int m board.length, n board[0].length; boolean[][] visited new boolean[m][n]; for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] word.charAt(0) dfs(board, word, i, j, 0, visited)) { return true; } } } return false; } private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) { if (index word.length()) { return true; } if (i 0 || i board.length || j 0 || j board[0].length) { return false; } if (visited[i][j] || board[i][j] ! word.charAt(index)) { return false; } visited[i][j] true; boolean found dfs(board, word, i 1, j, index 1, visited) || dfs(board, word, i - 1, j, index 1, visited) || dfs(board, word, i, j 1, index 1, visited) || dfs(board, word, i, j - 1, index 1, visited); visited[i][j] false; return found; }这道题的坑点在于回溯之后必须把访问标记还原。如果你忘了visited[i][j] false那么条路径一旦走死其他路径就再也不能使用这个格子了结果会漏掉正确答案。我第一次刷这道题就是漏了这行调试了半天才发现是“路径复用”问题。剪枝是这道题的另一个重点。最简单有效的剪枝是在进入DFS前先判断起点字符是否等于word.charAt(0)不等就直接跳过。更进一步你还可以在DFS内部提前判断当前字符与目标字符是否匹配。还有一个相对冷门但面试很加分的优化先统计矩阵里各字符的数量如果单词中某个字符的数量比矩阵里的还多直接返回false。这个做法叫字母频率预检对长单词场景效果很好。回溯类题目的时间复杂度一般比较高单词搜索最坏是O(mn * 4^L)其中L是单词长度。这个复杂度面试官知道他们更多想看你写DFS的细节是否规范。4.3 最大正方形、最小路径和二维DP的两个经典套路矩阵题里DP是一大门类。hot100里最值得做的两道基础题是最大正方形LeetCode 221和最小路径和LeetCode 64一个练“短板思维”一个练“转移方程”。先看最大正方形。题目给一个char[][]矩阵找只包含1的最大正方形的面积。朴素做法是暴力枚举枚举每个格子作为左上角然后不断扩大边长去检查时间复杂度O(mn * min(m, n))面试基本不给过。DP解法的关键是重新定义状态dp[i][j]表示以位置(i, j)作为右下角的正方形的最大边长。转移方程是if (matrix[i - 1][j - 1] 1) { dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1; }为什么要取三个方向的最小值再加1因为正方形要想以(i, j)为右下角扩展开它的上方、左方、左上方三个相邻位置都必须是足够大的正方形短板决定最终边长。我习惯把这类题总结成一句话正方形DP就看三方向最小值路径DP就看两个来源取最优。再来看最小路径和。题目给出一个grid从左上角走到右下角每次只能向右或向下求路径上数字之和的最小值。转移方程非常直白dp[i][j] grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]);因为走到(i, j)只能从上方或左方过来取其中较小的那个来源。边界条件也好处理第一行只能一直往右累加第一列只能一直往下累加。这两道题还有一个共同点都可以用滚动数组把空间从O(mn)降到O(n)。最大正方形只要保留上一行的dp值再加一个左上角的临时变量最小路径和更是只需要一维数组反复覆盖。面试的时候你把“原地DP”或者“滚动数组”写出来面试官眼睛会亮一下。不过第一次刷的时候我建议先老老实实写二维DP确保思路正确再优化空间不要一上来就挑战滚动数组那样debug会耗掉太多时间。5. 刷题避坑指南这五个坑我每个都踩过5.1 边界与索引的经典翻车点刷矩阵题这段时间我把踩过的坑整理成了一个自查表每次提交之前先扫一遍坑点现象解法for循环边界写错数组越界或漏遍历统一约定左闭右开要么左闭右闭别混用螺旋矩阵单行单列重复遍历结果多出重复元素底行和左列遍历前加top bottom、left right判断二分映射二维数组除错列数越界或定位错误行优先存储时mid / n是行mid % n是列DFS标记未还原搜索类结果错误回溯代码块结束时必须visited[i][j] false矩阵置零覆盖标记行结果全部错乱先用临时变量记录首行首列的原始状态这个表里每一个坑都是我真实debug过的。我最惨的一次是在mid / n那边写成了mid / m调试半小时没发现最后打印矩阵每一轮的mid值才恍然大悟。矩阵题就是这样错误往往不在逻辑框架而在细节索引而这种错误最难定位。5.2 面试过程中的细节决策刷题是一回事面试表现是另一回事。矩阵题在面试中出现频率很高但面试官其实不只看你最终代码对不对更看你的解题思路和沟通方式。我自己的经验是拿到矩阵题先做三件事第一确认矩阵的行列数取值范围以及是int[][]还是char[][]第二确认能不能修改原数组这决定了你能否用原地标记第三和面试官确认空间复杂度的要求这决定了你是用visited数组还是原地染色。写代码的时候先把框架写清楚再填边界条件。比如DFS先写越界判断再写访问标记再写递归调用最后写回溯还原。顺序对了代码自然清爽。还有一个小细节循环变量命名用row、col比用i、j更清晰尤其在复杂的矩阵题里可读性会好很多。面试现场代码风格好是真的有额外加分的。避坑的终极心法其实就一条提交之前手动用一个小矩阵把流程走一遍尤其关注单行、单列、全0、空矩阵这些极端输入。矩阵题的边界case往往就藏在这些极端输入里一次手动模拟能省下三次错误提交。6. 我对矩阵题的个人体会刷完hot100里这组矩阵题我最大的感受是矩阵题本质上考的还是“用变量描述状态”和“边界意识”。螺旋矩阵用四个边界变量描述剩余空间旋转图像用“转置翻转”两步描述旋转过程搜索二维矩阵II用“右上角走位”描述排除策略矩阵置零用“首行首列标记”描述空间复用。当你能把每一步的状态变量讲清楚代码正确率会大幅提升。最后分享一个小技巧我给自己整理了一套矩阵题通用模板包含四方向数组、边界判断、二维映射三个子工具。每次刷新的矩阵题我都是先看能不能套上这套工具再思考题目独特的约束。这套习惯帮我省下了大量调试时间。如果你也正在刷hot100我建议你亲手把这套模板写一遍而不是直接抄我的——只有自己踩过边界条件的坑才能在面试的时候稳稳避开。