Leetcode 54: 螺旋矩阵

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

---

适合面试的解法：边界法（层级遍历）

解法描述

1. 核心思想：一次遍历一圈，按四个边界移动指针
   • 定义四个边界：top, bottom, left, right，分别表示当前未遍历层的上边界、下边界、左边界和右边界。
   • 遍历一圈后，逐步缩小边界范围，直到所有元素都被处理。
2. 边界调整规则：
   • 从左到右遍历上侧（top 行），然后 top++；
   • 从上到下遍历右侧（right 列），然后 right--；
   • 如果还有未遍历的行，则 从右到左遍历底侧（bottom 行），然后 bottom--；
   • 如果还有未遍历的列，则 从下到上遍历左侧（left 列），然后 left++。
   • 每次遍历完一圈，都缩小边界范围。
3. 终止条件：
   • 当 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;}
}

---

复杂度分析

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

---

适用场景

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

---

其他解法及分析

解法 2：模拟法

---

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

思路

1. 定义方向和边界：
   • 使用方向数组 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 表示右、下、左、上的顺序；
   • 通过一个 dirIndex 控制当前的方向（如 dirIndex = 0 表示向右，dirIndex = 1 表示向下）。
   • 定义已经访问过的区域，并使用二维 visited 数组记录已经访问的元素。
2. 遍历矩阵：
   • 从 (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;}
}

---

复杂度分析

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

---

适用场景

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

---

快速AC总结

推荐解决方案

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

---

在面试中如何快速AC

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

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