Leetcode一百题——螺旋矩阵

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

1. 算法核心思想：物理模拟与“降维”标记

模拟了人类在矩阵中画螺旋线的物理过程：一直往前走，撞到墙壁或者撞到自己走过的路，就顺时针拐弯。 这道题传统的做法是开辟一个 O(M * N) 的布尔类型 visited 数组来记录走过的路径。但该解法敏锐地察觉到了测试用例的数据边界，直接将原矩阵中走过的格子篡改为越界值 101（充当路障）。这种“鸠占鹊巢”的做法，彻底消灭了额外的空间开销。

2. 代码拆解

• 上帝视角定步数：一开始直接算出矩阵的总格子数 total。因为无论怎么绕圈子，我们刚好只会走 total 步。这个绝对的循环上限，让我们完全不需要去写复杂的 while(true) 终止条件。

• 探路与行进（if 分支）：以当前方向 dir 前进时，程序就像雷达一样，永远先看一眼“前方下一个格子”：

  • 如果前方没有掉出矩阵悬崖（例如 nowx + 1 < cols 或 nowx - 1 >= 0），并且前方不是 101 墙壁。
  • 说明路是通的，直接吃掉脚下的数字存入 result，脚下踩成 101 废墟，然后大步向前走。

• 顺时针拐弯（else 分支）：

  • 如果前方没路了（越界或撞到了 101），说明我们正站在一个拐角上。
  • 吃掉这个拐角的数字，把它踩成 101。
  • 立刻将方向 dir 顺时针切换（0 -> 1 -> 2 -> 3 -> 0），并强行向新方向迈出一步。

3. 复杂度剖析

• 时间复杂度：O**(M×N)**。无论是直走还是拐弯，每一次循环严格处理一个格子，总循环次数完美等于矩阵元素的总数，执行时间呈极致的线性级别。
• 空间复杂度：O**(1)**。如果不把用于返回结果的 result 数组计算在内，整个算法仅仅申请了坐标和方向这几个常量级别的整形变量。