54. 螺旋矩阵

1. 题目简介

难度：中等，原题链接：54. 螺旋矩阵。

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

2. 问题分析

从左上角开始，按右、下、左、上的顺序行走。只要下一步会越界，或进入已经访问过的格子，就顺时针转向。重复这个过程，直到所有元素都加入结果。

代码用三个状态描述遍历过程：

• (i, j)：当前格子的行、列下标。
• t：当前方向，directions[t] 依次表示右、下、左、上。
• walked[i][j]：当前格子是否已经访问，0 表示尚未访问。

每次先把 matrix[i][j] 加入 res，并标记当前格子；再试算下一步的位置 nexti、nextj。如果下一步不可访问，就用 (t + 1) % 4 切换方向，然后按新的方向移动。

例如遍历完最上面一行，到达右上角后，再向右就会越界，因此转向下。走完外圈后，已访问的格子又会挡住继续向外走的路线，使遍历进入内圈。结果数量达到 m * n 时结束，单行和单列也遵循同一个停止条件。

3. 代码实现

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 记录元素是否已经被遍历过
        int[][] walked = new int[m][n];

        // 分别表示「右」、「下」、「左」、「上」四个方向，
        // t 用来记录当前遍历的方向 directions[t]
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int t = 0;

        // 记录当前遍历的元素
        int i = 0, j = 0;

        List<Integer> res = new ArrayList<>();
        // 添加的元素个数就是原始矩阵的总个数
        while (res.size() < m * n) {
            res.add(matrix[i][j]);
            walked[i][j]++;
            int nexti = i + directions[t][0];
            int nextj = j + directions[t][1];
            if (nexti < 0 || nexti >= m || nextj < 0 || nextj >= n || walked[nexti][nextj] > 0) {
                t = (t + 1) % 4;
            }
            i += directions[t][0];
            j += directions[t][1];
        }
        return res;
    }
}

4. 复杂度分析

• 时间复杂度：O(m × n)，所有元素各访问一次。
• 额外空间复杂度：O(m × n)，walked 记录每个格子是否访问过，不计返回结果。

5. 关联问题

矩阵的各种遍历方式：

1. 54. 螺旋矩阵
2. 59. 螺旋矩阵 II
3. 498. 对角线遍历

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明