Leetcode54:螺旋矩阵

Leetcode 54: 螺旋矩阵 是一道经典的矩阵遍历模拟题目，要求我们以螺旋顺序遍历一个二维数组。这个问题在面试中非常经典，考察模拟、数组操作以及逻辑清晰度。掌握本题的高效解法可以迅速给面试官留下好印象。

---

适合面试的解法：边界法（层级遍历） 解法描述 核心思想：一次遍历一圈，按四个边界移动指针 定义四个边界：top, bottom, left, right，分别表示当前未遍历层的上边界、下边界、左边界和右边界。遍历一圈后，逐步缩小边界范围，直到所有元素都被处理。 边界调整规则： 从左到右遍历上侧（top 行），然后 top++；从上到下遍历右侧（right 列），然后 right--；如果还有未遍历的行，则 从右到左遍历底侧（bottom 行），然后 bottom--；如果还有未遍历的列，则 从下到上遍历左侧（left 列），然后 left++。每次遍历完一圈，都缩小边界范围。 终止条件： 当 top > bottom 或 left > right 时，说明所有元素都已访问。

---

代码模板 import java.util.*; class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); if (matrix == null || 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 i = left; i <= right; i++) { result.add(matrix[top][i]); } top++; // 上边界缩小 // 从上到下遍历右边界 for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); } right--; // 右边界缩小 // 检查是否还有未遍历的行 if (top <= bottom) { // 从右到左遍历下边界 for (int i = right; i >= left; i--) { result.add(matrix[bottom][i]); } bottom--; // 下边界缩小 } // 检查是否还有未遍历的列 if (left <= right) { // 从下到上遍历左边界 for (int i = bottom; i >= top; i--) { result.add(matrix[i][left]); } left++; // 左边界缩小 } } return result; } }

---

复杂度分析 时间复杂度：O(m * n) 访问每个元素一次，m 为行数，n 为列数。 空间复杂度：O(1)（不计算结果集） 原地遍历，无需额外空间。

---

适用场景 面试首选解法： 模拟问题逻辑清晰，层次分明，行为可解释。高效，简单易实现，能快速写出来。 面试中可以结合剪枝优化、边界调整等细节，展示代码能力。

---

其他解法及分析 解法 2：模拟法

---

该解法直接按照螺旋的变化顺序（右 -> 下 -> 左 -> 上）模拟移动，通过控制方向实现遍历。

思路 定义方向和边界： 使用方向数组 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 表示右、下、左、上的顺序；通过一个 dirIndex 控制当前的方向（如 dirIndex = 0 表示向右，dirIndex = 1 表示向下）。定义已经访问过的区域，并使用二维 visited 数组记录已经访问的元素。 遍历矩阵： 从 (0, 0) 点开始，模拟按照当前方向移动；如果即将移动超出边界或者已经访问过，切换到下一个方向；直到所有元素遍历完为止。

---

代码模板 class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result; int m = matrix.length, n = matrix[0].length; boolean[][] visited = new boolean[m][n]; // 记录访问情况 // 定义方向数组（右、下、左、上） int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int dirIndex = 0; // 当前方向 int row = 0, col = 0; // 当前坐标 for (int i = 0; i < m * n; i++) { result.add(matrix[row][col]); visited[row][col] = true; // 计算下一个位置 int nextRow = row + dirs[dirIndex][0]; int nextCol = col + dirs[dirIndex][1]; // 如果越界或已经访问过，改变方向 if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol]) { dirIndex = (dirIndex + 1) % 4; // 顺时针切换方向 nextRow = row + dirs[dirIndex][0]; nextCol = col + dirs[dirIndex][1]; } row = nextRow; col = nextCol; } return result; } }

---

复杂度分析 时间复杂度：O(m * n) 每个元素遍历一次。 空间复杂度：O(m * n) 使用了 visited 二维数组记录访问情况。

---

适用场景 如果面试官要求实现更灵活的模拟法，则此解法是合适的替代。不过，由于需要额外的 visited 数组，其空间复杂度较高，不是首选。

---

快速AC总结 推荐解决方案 优先使用：边界法（解法 1） 模拟螺旋顺序，根据边界进行缩小调整；代码简洁高效，容易直接实现，完全满足面试需求。 备选模拟法（解法 2） 如果需要通过灵活控制方向和遍历行为进行实现，此解法较为通用，但需要额外空间。

---

在面试中如何快速AC 清晰描述解法： 解释如何依次遍历每一圈，使用上下左右边界标记矩阵；让面试官了解整个遍历顺序和边界调整的逻辑。 快速实现代码： 边界法（解法 1） 适合作为首选；模拟移动的代码少且简洁，更容易写。 关注边界条件： 注意矩阵为空的情况；单行单列、非方阵等特殊情况要覆盖。

通过掌握这两种解法，能够灵活应对问题，并快速在面试中实现清晰的解答，获得面试官肯定！