54. 螺旋矩阵

Posted on Edited on In Views: Word count in article: 635 Reading time ≈ 1 mins.

54. 螺旋矩阵

题目链接：54. 螺旋矩阵

题目描述

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

核心思考：模拟与边界收缩

这道题的核心是模拟螺旋遍历的过程：向右 -> 向下 -> 向左 -> 向上，然后不断循环。

  1. 设定方向：预定义四个方向的位移增量 DIR = (0,1), (1,0), (0,-1), (-1,0)。当遇到墙壁或走完一整条边时，按部就班切换下一个。
  2. 逻辑简化：
    • 每当我们走完当前方向的一整条边，我们就完成了一次“切削”。
    • 例如，从左往右走完第一行后，接下来的“下行”可走的长度会减 1。
    • 走完垂直的一条边后，“横行”可走的长度也会减 1。
    • 这种思路下，我们可以利用 n 和 m 的动态减少来控制循环。
  3. 流程：
    • 维护当前坐标 (i, j) 和当前方向索引 d。
    • 循环直至收集到所有共 size = m * n 个元素。
    • 在每个方向，根据当前的步数限制（最初横向走 n 步，纵向走 m-1 步等）进行步进，并将元素加入结果集。
    • 每次转向后，交换或收缩剩余可走的行/列数。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
DIR = (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 = 0
        j = -1 # 初始 j 设为 -1，方便第一步 j + 1 正确定位到 (0,0)
        d = 0
        
        while len(ans) < size:
            dx, dy = DIR[d]
            # 根据当前方向可以行进的步数（n）进行遍历
            for _ in range(n):
                i += dx
                j += dy
                ans.append(matrix[i][j])
            
            # 切换到下一个方向
            d = (d + 1) % 4
            # 关键：走完当前方向后，下一次交叉方向的可走空间减 1
            # 例如走完横向，纵向深度 m 就减 1，并交换 n,m 的角色
            n, m = m - 1, n

        return ans

复杂度分析

  • 时间复杂度：$O(M \times N)$，其中 $M$ 和 $N$ 为矩阵的行数和列数。我们需要且仅需完整地遍历矩阵中的每一个元素一次。
  • 空间复杂度：$O(1)$，如果不考虑作为结果返回的数组 ans，我们只使用了常数个索引和状态变量。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
2
3
4
5
m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    m, n = len(matrix), len(matrix[0])
            size = m * n
            ans = []
            i = 0
            j = -1 # 初始 j 设为 -1，方便第一步 j + 1 正确定位到 (0,0)
            d = 0

            while len(ans) < size:
                dx, dy = DIR[d]
                # 根据当前方向可以行进的步数（n）进行遍历
                for _ in range(n):
                    i += dx
                    j += dy
                    ans.append(matrix[i][j])

                # 切换到下一个方向
                d = (d + 1) % 4
                # 关键：走完当前方向后，下一次交叉方向的可走空间减 1
                # 例如走完横向，纵向深度 m 就减 1，并交换 n,m 的角色
                n, m = m - 1, n

            return ans

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.spiralOrder(matrix)
    for v in result:\n        print(v, end=' ')\n    print()

if __name__ == "__main__":
    main()

运行示例：

1
echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py