LeetCode 54.螺旋矩阵遍历的两种方法详解与对比

本文介绍两种Java实现螺旋矩阵遍历的算法，并对其时间和空间复杂度、实现思路及适用场景进行对比。螺旋矩阵遍历要求按照顺时针方向依次访问矩阵中的每一个元素。例如，对于以下矩阵：

[[1, 2, 3],[4, 5, 6],[7, 8, 9]
]

螺旋遍历结果为 [1, 2, 3, 6, 9, 8, 7, 4, 5]。

---

方法一：边界调整法（逐层收缩）

实现思路

1. 定义四个边界：上边界（top）、下边界（bottom）、左边界（left）、右边界（right）。
2. 逐层遍历：按顺时针方向遍历每一层的四个边，每次遍历后调整对应的边界。
3. 终止条件：当所有元素都被访问后退出循环。

代码实现

import java.util.ArrayList;
import java.util.List;class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> res = new ArrayList<>();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;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++) {res.add(matrix[top][i]);}top++;// 从上到下遍历右边界for (int i = top; i <= bottom; i++) {res.add(matrix[i][right]);}right--;// 从右到左遍历下边界（如果存在）if (top <= bottom) {for (int i = right; i >= left; i--) {res.add(matrix[bottom][i]);}bottom--;}// 从下到上遍历左边界（如果存在）if (left <= right) {for (int i = bottom; i >= top; i--) {res.add(matrix[i][left]);}left++;}}return res;}
}

复杂度分析

• 时间复杂度：O(m×n)，每个元素仅访问一次。
• 空间复杂度：O(1)，仅使用固定变量记录边界。

---

方法二：矩阵旋转法（逐层剥离）

实现思路

1. 逐层剥离：每次取矩阵的第一行加入结果。
2. 逆时针旋转剩余矩阵：将剩余部分逆时针旋转90度，重复操作直到矩阵为空。
3. 旋转实现：逆时针旋转通过反转每行后转置实现。

代码实现

import java.util.ArrayList;
import java.util.List;class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> res = new ArrayList<>();if (matrix == null || matrix.length == 0) return res;int[][] current = matrix;while (current.length > 0) {// 添加第一行到结果for (int num : current[0]) {res.add(num);}// 移除第一行，得到剩余矩阵int[][] remaining = new int[current.length - 1][];for (int i = 1; i < current.length; i++) {remaining[i - 1] = current[i];}// 逆时针旋转剩余矩阵current = rotateCounterClockwise(remaining);}return res;}// 逆时针旋转90度private int[][] rotateCounterClockwise(int[][] matrix) {if (matrix.length == 0) return new int[0][0];int m = matrix.length, n = matrix[0].length;// 反转每行int[][] reversed = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {reversed[i][j] = matrix[i][n - 1 - j];}}// 转置矩阵int[][] rotated = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {rotated[i][j] = reversed[j][i];}}return rotated;}
}

复杂度分析

• 时间复杂度：O(n³)，每次旋转需要遍历矩阵两次（反转和转置）。
• 空间复杂度：O(n²)，每次旋转需创建新矩阵。

---

方法对比

对比维度	边界调整法	矩阵旋转法
时间复杂度	O(m×n)	O(n³)
空间复杂度	O(1)	O(n²)
实现难度	中等（需处理边界条件）	简单（逻辑直观）
适用场景	大规模矩阵	小规模矩阵或算法教学
优势	高效，无需额外空间	代码简洁，无需复杂边界判断
劣势	需处理多层边界条件	频繁旋转导致性能低下

---

总结

1. 边界调整法：
   适合实际应用场景，尤其是大规模矩阵遍历。通过逐层收缩边界，时间和空间复杂度均最优。

2. 矩阵旋转法：
   适合理解螺旋遍历的逻辑本质，但时间和空间开销较大，仅推荐在小规模数据或教学场景使用。

两种方法各有优劣，开发者可根据具体需求选择实现方式。若追求性能，优先选择边界调整法；若需快速验证逻辑，可尝试矩阵旋转法。