螺旋矩阵 | 秋招知识库

总体思路

根据题意，我们从左上角 $(0, 0)$ 出发，按照「右下左上」的顺序前进：

首先向右走，如果到达矩阵边界，则向右转 $90^{\circ}$ ，前进方向变为向下。
然后向下走，如果到达矩阵边界，则向右转 $90^{\circ}$ ，前进方向变为向左。
然后向左走，如果到达矩阵边界，则向右转 $90^{\circ}$ ，前进方向变为向上。
然后向上走，先从 $7$ 走到 $4$ ，然后从 $4$ 准备向上走，但上面的 $1$ 是一个已经访问过的数字，那么向右转 $90^{\circ}$ ，前进方向变为向右。
重复上述过程，直到答案的长度为 $m n$ 。

方法一：标记

对于已经访问过的数字，可将其标记为 $\infty$ 或者空，从而避免重复访问。
用一个长为 $4$ 的方向数组 $DIRS = [(0, 1), (1, 0), (0, - 1), (- 1, 0)]$ 分别表示右下左上 $4$ 个方向。同时用一个下标 $di$ 表示当前方向，初始值为 $0$ ，表示一开始向右。
每次移动，相当于把行号增加 $DIRS [di] [0]$ ，把列号增加 $DIRS [di] [1]$ 。
向右转 $90^{\circ}$ ，相当于把 $di$ 增加 $1$ ，但在 $di = 3$ 时要回到 $di = 0$ 。两种情况合二为一，把 $di$ 更新为 $(di + 1) mod 4$ 。

Python 解法1C++ 解法1

python

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 右下左上

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        ans = []
        i = j = di = 0
        for _ in range(m * n):  # 一共走 mn 步
            ans.append(matrix[i][j])
            matrix[i][j] = None  # 标记，表示已经访问过（已经加入答案）
            x, y = i + DIRS[di][0], j + DIRS[di][1]  # 下一步的位置
            # 如果 (x, y) 出界或者已经访问过
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None:
                di = (di + 1) % 4  # 右转 90°
            i += DIRS[di][0]
            j += DIRS[di][1]  # 走一步
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ans(m * n);
        int i = 0, j = 0, di = 0;
        for (int k = 0; k < m * n; k++) { // 一共走 mn 步
            ans[k] = matrix[i][j];
            matrix[i][j] = INT_MAX; // 标记，表示已经访问过（已经加入答案）
            int x = i + DIRS[di][0];
            int y = j + DIRS[di][1]; // 下一步的位置
            // 如果 (x, y) 出界或者已经访问过
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == INT_MAX) {
                di = (di + 1) % 4; // 右转 90°
            }
            i += DIRS[di][0];
            j += DIRS[di][1]; // 走一步
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (m n)$ ，其中 $m$ 和 $n$ 分别为 $matrix$ 的行数和列数。
空间复杂度： $O (1)$ 。返回值不计入。

方法二：不标记

上面的做法需要修改 $matrix$ ，能否不修改呢？

示例 2 这 $12$ 个数字，可以分为以下 $5$ 组：

$1 \to 2 \to 3 \to 4$
$8 \to 12$
$11 \to 10 \to 9$
$5$
$6 \to 7$

其中第 $1, 3, 5$ 组都是向右或者向左走的，长度依次为 $4, 3, 2$ ，这是一个从 $n = 4$ 开始的逐渐递减的序列。

其中第 $2, 4$ 组都是向下或者向上走的，长度依次为 $2, 1$ ，这是一个从 $m - 1 = 2$ 开始的逐渐递减的序列。

由于走的步数是有规律的，我们可以精确地控制在每个方向上要走多少步，无需判断是否出界、是否重复访问：

从 $(0, - 1)$ 开始。
一开始，向右走 $n$ 步，每次先走一步，再把数字加入答案。走 $n$ 步即 $1 \to 2 \to 3 \to 4$ ，矩阵第一排的数都加入了答案。
然后向下走 $m - 1$ 步，即 $8 \to 12$ 。
然后向左走 $n - 1$ 步，即 $11 \to 10 \to 9$ 。
然后向上走 $m - 2$ 步，即 $5$ 。
然后向右走 $n - 2$ 步，即 $6 \to 7$ 。
重复上述过程，直到答案的长度等于 $m n$ 。

代码实现时，可以这样简化代码：

一开始走 $n$ 步。
把 $m, n$ 分别更新为 $n, m - 1$ ，这样下一轮循环又可以走 $n$ 步（相当于走了 $m - 1$ 步），无需修改其他逻辑。相当于撕掉矩阵的第一行，把矩阵旋转 $90^{\circ}$ 后，对这个 $n$ 行 $m - 1$ 列的新矩阵继续做同样的操作。
把 $m, n$ 分别更新为 $n, m - 1$ ，这样下一轮循环又可以走 $n$ 步（相当于走了 $n - 1$ 步）。
把 $m, n$ 分别更新为 $n, m - 1$ ，这样下一轮循环又可以走 $n$ 步（相当于走了 $m - 2$ 步）。
依此类推，每次只需把 $m, n$ 分别更新为 $n, m - 1$ 即可。

答疑

问：如何说明这个规律的正确性？

答：在上文的例子中，我们把示例 2 分成了 $5$ 组。一般地，每 $4$ 组，我们会把矩阵最外面一圈去掉（就像剥洋葱），矩阵的行数会减少 $2$ ，列数会减少 $2$ 。所以行列的减少是有规律的。

Python 解法3C++ 解法3

python

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 右下左上

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        size = m * n
        ans = []
        i, j, di = 0, -1, 0  # 从 (0, -1) 开始
        while len(ans) < size:
            dx, dy = DIRS[di]
            for _ in range(n):  # 走 n 步（注意 n 会减少）
                i += dx
                j += dy  # 先走一步
                ans.append(matrix[i][j])  # 再加入答案
            di = (di + 1) % 4  # 右转 90°
            m, n = n, m - 1  # 减少后面的循环次数（步数）
        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int size = m * n;
        vector<int> ans;
        int i = 0, j = -1; // 从 (0, -1) 开始
        for (int di = 0; ans.size() < size; di = (di + 1) % 4) {
            for (int k = 0; k < n; k++) { // 走 n 步（注意 n 会减少）
                i += DIRS[di][0];
                j += DIRS[di][1]; // 先走一步
                ans.push_back(matrix[i][j]); // 再加入答案
            }
            m--; // 减少后面的循环次数（步数）
            swap(n, m);
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (m n)$ ，其中 $m$ 和 $n$ 分别为 $matrix$ 的行数和列数。
空间复杂度： $O (1)$ 。返回值不计入。

思考题

假如 $m \leq 10^{9}, n \leq 10^{9}$ 。

输出走了 $k$ 步之后，你所在的格子的坐标（行列编号）。

你能用 $O (\log)$ 或者 $O (1)$ 时间解决吗？

欢迎在评论区分享你的思路/代码。

相似题目（数字表示难度分）

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

总体思路 ​

方法一：标记 ​

复杂度分析 ​

方法二：不标记 ​

答疑 ​

复杂度分析 ​

思考题 ​

相似题目（数字表示难度分） ​

分类题单 ​

总体思路

方法一：标记

复杂度分析

方法二：不标记

答疑

复杂度分析

思考题

相似题目（数字表示难度分）

分类题单