【LeetCode HOT100】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解题思路这道题的核心是模拟顺时针螺旋遍历的过程。常见的有两种思路方向数组模拟行走用一个方向数组控制移动方向遇到边界或已访问格子就转向。边界收缩法推荐维护上下左右四个边界每遍历完一条边就收缩对应边界像剥洋葱一样逐层处理。下面分别讲解这两种方法。解法一方向数组模拟行走思路分析我们可以把整个过程想象成一个人在矩阵中行走起始位置(0, 0)初始方向向右按照右 → 下 → 左 → 上 → 右 …的顺序循环改变方向当下一步会越界或走到已经访问过的格子时就顺时针转向重复直到走完所有格子方向设计用二维数组表示四个方向javaint[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 索引0:右 索引1:下 索引2:左 索引3:上用directionIndex表示当前方向索引需要转向时javadirectionIndex (directionIndex 1) % 4; // 0→1→2→3→0代码实现javaclass 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, cols matrix[0].length; boolean[][] visited new boolean[rows][cols]; int total rows * cols; int row 0, col 0; int[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int dirIdx 0; // 初始向右 for (int i 0; i total; i) { order.add(matrix[row][col]); visited[row][col] true; // 试探下一步 int nextRow row directions[dirIdx][0]; int nextCol col directions[dirIdx][1]; // 如果下一步越界或已访问就转向 if (nextRow 0 || nextRow rows || nextCol 0 || nextCol cols || visited[nextRow][nextCol]) { dirIdx (dirIdx 1) % 4; } // 移动 row directions[dirIdx][0]; col directions[dirIdx][1]; } return order; } }复杂度分析时间复杂度O(m×n)每个元素访问一次空间复杂度O(m×n)visited 数组的大小解法二边界收缩法推荐思路分析定义四个边界left左边界列索引right右边界列索引top上边界行索引bottom下边界行索引每一轮按顺序遍历四条边从左到右遍历上边界top行从left到right从上到下遍历右边界right列从top1到bottom如果left right且top bottom避免单行/单列重复从右到左遍历下边界bottom行从right-1到left1从下到上遍历左边界left列从bottom到top1收缩边界leftright--topbottom--重复以上步骤直到left right或top bottom。图解示例以 3×3 矩阵为例text初始: left0, right2, top0, bottom2 第1圈 ① → 1 2 3 ② ↓ 6 9 ③ ← 8 ④ ↑ 7 4 收缩: left1, right1, top1, bottom1 第2圈 ① → 5 收缩: left2, right0, top2, bottom0 → 结束代码实现javaclass 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, cols matrix[0].length; int left 0, right cols - 1; int top 0, bottom rows - 1; while (left right top bottom) { // 上边界左 → 右 for (int col left; col right; col) { order.add(matrix[top][col]); } // 右边界上 → 下跳过右上角 for (int row top 1; row bottom; row) { order.add(matrix[row][right]); } // 如果不是单行或单列才继续遍历下边界和左边界 if (left right top bottom) { // 下边界右 → 左跳过右下角 for (int col right - 1; col left; col--) { order.add(matrix[bottom][col]); } // 左边界下 → 上跳过左下角和左上角 for (int row bottom; row top; row--) { order.add(matrix[row][left]); } } // 收缩边界 left; right--; top; bottom--; } return order; } }为什么需要if (left right top bottom)考虑两种特殊情况单行矩阵[[1,2,3]]遍历完上边界和右边界后如果继续遍历下边界和左边界会导致重复添加元素。判断条件中的top bottom不成立0 0为 false所以跳过正确。单列矩阵[[1],[2],[3]]left right不成立0 0为 false跳过下边界和左边界正确。复杂度分析时间复杂度O(m×n)每个元素访问一次空间复杂度O(1)只用了常数个额外变量两种解法对比特性方向数组法边界收缩法核心思想模拟行走转向检测剥洋葱收缩边界辅助空间O(m×n) visited数组O(1) 四个变量代码复杂度较简洁但需理解转向逻辑直观清晰适用场景通用通用尤其适合面试推荐边界收缩法更直观空间复杂度更优是面试中的首选写法。总结螺旋矩阵遍历是一道经典的模拟过程题目关键是理清遍历顺序和边界条件。两种方法本质相同都是一圈一圈地处理只是实现方式不同。边界收缩法通过维护四个边界变量避免了额外的 visited 数组更优雅。注意处理单行和单列矩阵的边界情况。相关链接题目链接LeetCode 54. 螺旋