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)

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，我们只使用了常数个索引和状态变量。