【LeetCode热题100】54. 螺旋矩阵——Java多解法详解

一、题目描述题目链接54. 螺旋矩阵难度中等题目描述给你一个m行n列的矩阵matrix请按照顺时针螺旋顺序返回矩阵中的所有元素。示例 1text输入matrix [[1,2,3],[4,5,6],[7,8,9]] 输出[1,2,3,6,9,8,7,4,5]示例 2text输入matrix [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出[1,2,3,4,8,12,11,10,9,5,6,7]提示m matrix.lengthn matrix[i].length1 m, n 10-100 matrix[i][j] 100二、思路分析这道题要求按顺时针螺旋顺序遍历矩阵本质上是一个模拟过程的问题。我们可以把遍历过程想象成一个人沿着矩阵的边界行走遇到障碍就右转。核心难点转向时机什么时候从向右转为向下边界处理如何避免重复访问终止条件何时遍历完成特殊形状单行、单列矩阵如何处理两种主流解法解法核心思想空间复杂度推荐程度方向模拟法模拟行走用visited数组记录O(m×n)⭐⭐⭐按层遍历法边界收缩剥洋葱式遍历O(1)⭐⭐⭐⭐⭐三、解法一方向模拟法3.1 思路将遍历过程想象成一个机器人在矩阵中行走起始位置(0, 0)初始方向向右按照右 → 下 → 左 → 上 → 右 …的顺序循环改变方向当下一步会越界或走到已经访问过的格子时就顺时针转向重复直到走完所有格子3.2 方向设计用二维数组表示四个方向javaint[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 索引0: 向右 (row不变, col1) // 索引1: 向下 (row1, col不变) // 索引2: 向左 (row不变, col-1) // 索引3: 向上 (row-1, col不变)转向公式directionIndex (directionIndex 1) % 4实现 0→1→2→3→0 的循环切换。3.3 代码实现javaimport java.util.*; class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger order new ArrayList(); if (matrix null || matrix.length 0 || matrix[0].length 0) { return order; } int rows matrix.length; int cols matrix[0].length; boolean[][] visited new boolean[rows][cols]; int total rows * cols; // 方向数组右、下、左、上 int[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int directionIndex 0; // 初始方向向右 int row 0, col 0; for (int i 0; i total; i) { order.add(matrix[row][col]); visited[row][col] true; // 试探下一步 int nextRow row directions[directionIndex][0]; int nextCol col directions[directionIndex][1]; // 如果下一步越界或已访问就转向 if (nextRow 0 || nextRow rows || nextCol 0 || nextCol cols || visited[nextRow][nextCol]) { directionIndex (directionIndex 1) % 4; } // 移动到下一个位置 row directions[directionIndex][0]; col directions[directionIndex][1]; } return order; } }3.4 执行流程图解以matrix [[1,2,3],[4,5,6],[7,8,9]]为例步骤(row,col)添加的值当前方向下一步是否转向0(0,0)1右(0,1)否1(0,1)2右(0,2)否2(0,2)3右(0,3)是越界→ 转向下3(1,2)6下(2,2)否4(2,2)9下(3,2)是越界→ 转向左5(2,1)8左(2,0)否6(2,0)7左(2,-1)是越界→ 转向上7(1,0)4上(0,0)是已访问→ 转向右8(1,1)5右(1,2)是已访问→ 转向下最终结果[1,2,3,6,9,8,7,4,5]✅3.5 复杂度分析时间复杂度O(m×n)每个元素访问一次空间复杂度O(m×n)需要 visited 数组记录访问状态四、解法二按层遍历法推荐4.1 思路将矩阵看作一个洋葱从外向内一层一层地遍历。定义四个边界变量left左边界列索引right右边界列索引top上边界行索引bottom下边界行索引每轮遍历按顺序走四条边上边从左到右行 top右边从上到下列 right跳过右上角下边从右到左行 bottom跳过右下角左边从下到上列 left跳过左下角遍历完一圈后收缩边界leftright--topbottom--继续下一圈直到left right或top bottom。4.2 为什么需要条件判断javaif (left right top bottom)这个条件是为了处理单行或单列矩阵防止重复遍历单行矩阵[[1,2,3]]top bottomtop bottom不成立跳过下边和左边不会重复添加。单列矩阵[[1],[2],[3]]left rightleft right不成立跳过下边和左边正确。4.3 代码实现javaimport java.util.*; class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger order new ArrayList(); if (matrix null || matrix.length 0 || matrix[0].length 0) { return order; } int rows matrix.length; int cols matrix[0].length; int left 0, right cols - 1; int top 0, bottom rows - 1; while (left right top bottom) { // 1. 上边界从左到右 for (int col left; col right; col) { order.add(matrix[top][col]); } // 2. 右边界从上到下跳过右上角 for (int row top 1; row bottom; row) { order.add(matrix[row][right]); } // 3. 下边界和左边界仅当存在内部区域时才遍历 if (left right top bottom) { // 3a. 下边界从右到左跳过右下角 for (int col right - 1; col left; col--) { order.add(matrix[bottom][col]); } // 3b. 左边界从下到上跳过左下角 for (int row bottom; row top; row--) { order.add(matrix[row][left]); } } // 4. 收缩边界 left; right--; top; bottom--; } return order; } }4.4 执行流程图解以 3×3 矩阵为例text初始状态 left0, right2, top0, bottom2 第1圈遍历 ① 上边top0left→right[1,2,3] ② 右边right2top1→bottom[6,9] ③ 下边bottom2right-1→left1[8] ④ 左边left0bottom→top1[7,4] 收缩后 left1, right1, top1, bottom1 第2圈遍历 ① 上边[5] ② 右边无top12 bottom1 ③ 下边条件不满足left1, right1leftright不成立 ④ 左边无 收缩后left2, right0, top2, bottom0 循环结束结果[1,2,3,6,9,8,7,4,5]4.5 另一种写法如果你更喜欢用while(true)配合 break 的写法可以参考以下代码javaclass Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger list new ArrayList(); int m matrix.length; int n matrix[0].length; int up 0, down m - 1, left 0, right n - 1; while (true) { // 上边界 for (int i left; i right; i) list.add(matrix[up][i]); if (up down) break; // 右边界 for (int i up; i down; i) list.add(matrix[i][right]); if (--right left) break; // 下边界 for (int i right; i left; i--) list.add(matrix[down][i]); if (--down up) break; // 左边界 for (int i down; i up; i--) list.add(matrix[i][left]); if (left right) break; } return list; } }4.6 复杂度分析时间复杂度O(m×n)每个元素恰好访问一次空间复杂度O(1)只用了常数个额外变量五、解法对比总结维度方向模拟法按层遍历法核心思想模拟行走转向检测剥洋葱边界收缩代码长度较短稍长但清晰辅助空间O(m×n) visited数组O(1) 四个变量边界处理通过转向自动处理需要手动判断单行/单列理解难度中等需理解转向逻辑简单直观面试推荐度⭐⭐⭐⭐⭐⭐⭐⭐建议在面试中优先使用按层遍历法它空间复杂度更优逻辑也更清晰易懂。六、面试高频追问Q1如何处理单行或单列矩阵按层遍历法通过if (left right top bottom)条件判断来避免重复遍历。当矩阵为单行时top bottom条件不成立不会执行下边和左边的遍历。Q2如果要求不能用额外空间除了返回值按层遍历法本身就是 O(1) 额外空间符合要求。Q3能否用递归实现可以每层处理完边界后递归调用处理内层矩阵但递归深度受矩阵大小限制且不如迭代高效。七、相关题目推荐59. 螺旋矩阵 II - 螺旋矩阵的逆过程生成螺旋矩阵885. 螺旋矩阵 III - 在无限网格上螺旋遍历剑指 Offer 29. 顺时针打印矩阵 - 本题的剑指 Offer 版本八、参考资料官方题目链接54. 螺旋矩阵 - 力扣LeetCode官方题解链接54. 螺旋矩阵 - 官方题解