题目描述

给定一个包含 m x n 个元素的矩阵（m 行 n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

样例

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

算法

(模拟) $O(nm)$

1. 定义四个方向的常数方向数组 dir，不妨假设 0 表示方向为向右，1 为向下，2 为向左，3 为向上。
2. 定义二维数组 vis，代表该位置是否被访问过。
3. 从坐标 (0, 0) 开始，初始方向为 0。
4. 每次遍历后枚举下一个可行的方向是哪个，可行是指下一个位置没有被访问过。如果四个方向都不可行，则遍历结束。

时间复杂度

• 每个位置仅遍历一次，且寻找方向的时间复杂度是常数，故总时间复杂度 为$O(n)$。

空间复杂度

• 需要额外 $O(nm)$ 的空间存储 vis 数组。

C++ 代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        const int dir[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // dir为方向数组。

        int n = matrix.size(), m;
        if (n == 0)
            return {};

        m = matrix[0].size();
        vector<vector<int>> vis(n);
        vector<int> ans;

        for (int i = 0; i < n; i++) {
            vis[i].resize(m);
            for (int j = 0; j < m; j++)
                vis[i][j] = false;
        }

        int cur_d = 0, cur_x = 0, cur_y = 0;
        while (1) {
            vis[cur_x][cur_y] = true;
            ans.push_back(matrix[cur_x][cur_y]);
            bool flag = false;

            for (int i = 0; i < 4; i++) { // 枚举下一个可行的位置。
                int next_x = cur_x + dir[(i + cur_d) % 4][0];
                int next_y = cur_y + dir[(i + cur_d) % 4][1];

                if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m
                    || vis[next_x][next_y])
                    continue;

                flag = true;
                cur_x = next_x;
                cur_y = next_y;
                cur_d = (cur_d + i) % 4;
                break;
            }

            if (!flag)
                break;
        }

        return ans;
    }
};