leetcode-go/矩阵/19-螺旋矩阵.md

tags, create time

tags	create time
LeetCode 矩阵 中等	2026-05-17 13:53

19-螺旋矩阵

题面

LeetCode 54. Spiral Matrix

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

示例 1：

输入：matrix = [[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 ]]
结果：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]

直观理解遍历路径：
[[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

---

思路

[!question] 💡 什么是"顺时针螺旋"？

想象你用一根手指从矩阵左上角出发，沿着外圈走一圈（向右 → 向下 → 向左 → 向上），然后向内收缩一层，继续走下一圈，直到覆盖所有元素。

flowchart TD
    A["外层：向右走完顶行<br/>向下走完右列<br/>向左走完底行<br/>向上走完左列"] --> B["缩进一层"]
    B --> C["内层：重复同样四步"]
    C --> D{"还有没走的格子?"}
    D -->|"是"| B
    D -->|"否"| E["结束"]

[!abstract] 🗺️ 核心抽象：四面墙模型

与其追踪每个坐标 (i, j) 的复杂转向逻辑，不如把问题看作 四面不断缩进的墙：

边界变量	含义	初始值
top	已访问的最上行	0
bottom	未访问的最下行	m - 1
left	已访问的最左列	0
right	未访问的最右列	n - 1

每走完一条边，对应的一面墙就向内移动一格。当四面墙相遇（遍历完全部 m × n 个元素）时停止。

[!step] 算法流程

每一轮迭代中按固定顺序走四面：

1. 向右：从 left 走到 right，处理第 top 行。完成后 top++（顶墙下移）。
2. 向下：从 top 走到 bottom，处理第 right 列。完成后 right--（右墙左移）。
3. 向左：从 right 走到 left，处理第 bottom 行。完成后 bottom--（底墙上移）。
4. 向上：从 bottom 走到 top，处理第 left 列。完成后 left++（左墙右移）。

[!danger] ⚠️ 最容易出错的陷阱：重叠边

当剩余区域退化为一行或一列时，两步会操作同一个位置！

比如 3 × 3 矩阵，第一圈走完后只剩中间的 [5]。第二圈：

• 向右走：拿到 5，此时 top > bottom，已经没有第二行了
• 如果继续向下走——还是走 [5]！这就重复了

所以每一步开始前必须检查：剩余的矩形是否还有效（即 top <= bottom 且 left <= right）。

[!example] 🔍 逐步跟踪演示

以 matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]（3 行 4 列）为例：

初始化： top=0, bottom=2, left=0, right=3，结果 []

第一轮（走外圈）

步骤	方向	遍历范围	加入结果	边界更新后
①	→ 向右	第 0 行：j=0→3	[1,2,3,4]	top=1
②	↓ 向下	第 3 列：i=1→2	[1,2,3,4,8,12]	right=2
③	← 向左	第 2 行：j=2→0	[1,2,3,4,8,12,11,10,9]	bottom=1
④	↑ 向上	第 0 列：i=1→1	[1,2,3,4,8,12,11,10,9,5]	left=1

第二轮（剩内部 1×3 区域）

此时 top=1, bottom=1, left=1, right=2

步骤	方向	检查条件	遍历范围	加入结果	边界更新后
①	→ 向右	top(1) ≤ bottom(1) ✅	第 1 行：j=1→2	[...,6,7]	top=2
②	↓ 向下	top(2) ≤ bottom(1) ❌	—（跳过）	—	—
③	← 向左	left(1) ≤ right(2) ✅	第 1 行：j=2→1	但这一步应该先检查吗？

等等——让我重新审视第二步之后的情况：top=2, bottom=1，矩形高度为负，已经无效了。

实际上在第②步前就应该发现 top > bottom，直接终止整个循环更简洁。但按标准写法，我们可以在第②③④步各自加检查。

不过更好的办法是：在第四步之后检查结果长度是否等于 m*n，这样只需在每个大步骤前做轻量判断。

让我们换一种常见的实现策略来避免混乱——在每次走之前检查该方向是否还有空间：

Round 2 (top=1, bottom=1, left=1, right=2):

① top(1) ≤ bottom(1)，向右走 j∈[1,2]: matrix[1][1]=6, matrix[1][2]=7
   → 结果: [...,6,7]
   → top=2

② top(2) ≤ bottom(1)? NO → 跳过向下
③ left(1) ≤ right(2) 且 top(2) ≤ bottom(1)? NO → 跳过向左
④ left(1) ≤ right(2) 且 top(2) ≤ bottom(1)? NO → 跳过向上

完成！结果共 12 个元素 ✅

最终输出：[1,2,3,4,8,12,11,10,9,5,6,7] ✅

---

方法一：边界收缩法（推荐）⭐⭐⭐

[!abstract] 🎯 为什么这是最优解？

• 时间 O(mn)：每个元素恰好被访问一次
• 空间 O(1)：额外空间仅四个整数变量（不计返回值）
• 无需修改原矩阵：不破坏输入数据
• 代码简洁：四步循环清晰对称，不容易出错

[!note] 📐 关键设计决策

对于第三步（向左）和第四步（向上），它们只在仍有至少两行 AND 两列时有意义。因为在只剩一行或一列的情况下，第一步（向右）已经把该行/列完全覆盖了，后续步骤会产生重叠。

情况 A：剩 1 行 → 第一步向右已全部取完，第③步向左会重复
情况 B：剩 1 列 → 第二步向下已全部取完，第④步向上会重复

因此：

• 第③步额外要求 top < bottom（严格小于，确保至少两行）
• 第④步额外要求 left < right（严格小于，确保至少两列）

---

方法二：方向模拟法（备用方案）

[!question] 💡 另一种思路：用 direction array + visited set

定义 4 个方向向量 [(0,1), (1,0), (0,-1), (-1,0)]（右、下、左、上），用一个 visited 集合标记走过的格子。每次尝试沿当前方向继续走一步，如果越界或已访问则右转 90°。

[!quote] ❌ 为什么不推荐这个方法？

• 需要 O(mn) 的额外 visited 空间（或牺牲性地修改原矩阵）
• 每次都要判断"能否直走"和"是否要转弯"，逻辑更复杂
• 虽然代码行数不多，但可读性和效率都不如边界收缩法

[!success] ✅ 适用场景

这种方法适合变体题目——比如 "螺旋矩阵 II"（LeetCode 59，要求生成一个螺旋排列的 n x n 矩阵），这时没有现成的矩阵可以利用，需要自己构造。但对于本题的读取场景，边界收缩法是最佳选择。

---

代码提示

[!abstract] 📝 伪代码框架（边界收缩法）

result := []
top, left := 0, 0
bottom, right := m-1, n-1

for len(result) < m * n:

    // ① 向右走：top 行
    for j from left to right:
        result.append(matrix[top][j])
    top++

    // ② 向下走：right 列
    for i from top to bottom:
        result.append(matrix[i][right])
    right--

    // ③ 向左走：bottom 行（必须有至少两行）
    if top < bottom:
        for j from right down to left:
            result.append(matrix[bottom][j])
        bottom--

    // ④ 向上走：left 列（必须有至少两列）
    if left < right:
        for i from bottom down to top:
            result.append(matrix[i][left])
        left++

return result

[!warning] ⚠️ Go 实现中的常见坑

1. 切片预分配容量——提前 make([]int, 0, m*n) 可以避免运行时扩容，性能更好。
2. 第三个 for 循环是递减的——Go 不支持 for j := right; j >= left; j-- 这种原生语法，需要用显式声明 j 的 for 语句。
3. 递增变量的边界检查——在 top++ / right-- 之后立即影响后续循环的范围，这是正确性的核心。务必保持检查顺序：先递增/递减，再进入下一步时用新的值判断。

---

技巧

[!tip] 🔑 核心模式：边界收缩法（Bounded Expansion/Contraction）

遇到矩阵的蛇形/螺旋/锯齿遍历时，用四条边界线裁剪可行区域 是最直观的建模方式。每一步操作完一面后缩小该维度的范围，直到区域消失。

这个模式的本质是把二维空间压缩成一维序列的过程可视化——类似剥洋葱，一层一层往里。

[!note] 🐹 Go 语言中的注意事项

• Go 的切片是引用类型，返回值 []int 不会意外污染原矩阵
• 递减索引循环的惯用写法：

  for j := right; j >= left; j-- {
      result = append(result, matrix[bottom][j])
  }
  

• append 到预分配容量的切片性能更好，但非必填优化

[!info] 📊 两种方法对比

方法	时间复杂度	额外空间	是否需要修改原矩阵	推荐度
边界收缩	O(mn)	O(1)	不需要	⭐⭐⭐
方向+visited	O(mn)	O(mn)	不需要	⭐

[!quote] 💬 思维延伸

"剥洋葱"思维不仅适用于螺旋遍历：

• 锯齿遍历（Zigzag / Row Zigzag）：交替控制从左到右 / 从右到 left 的方向标志，配合上下边界收缩
• 旋转矩阵：同样是按层处理，每层 4 个角的循环交换
• 单词搜索的回溯题：也是逐层深入、回溯时恢复状态，与"剥层"思想异曲同工

核心心法是：把二维操作拆解成维度独立的约束，用边界变量来表达"还可以走多远"。

---

代码

// spiralOrder 按顺时针螺旋顺序返回矩阵的所有元素。
// 使用边界收缩法，额外空间 O(1)。
func spiralOrder(matrix [][]int) []int {
	m, n := len(matrix), len(matrix[0])
	result := make([]int, 0, m*n) // 预分配容量，避免多次扩容

	top, bottom := 0, m-1
	left, right := 0, n-1

	for len(result) < m*n {
		// ── ① 向右：遍历 top 行，从 left → right ──
		for j := left; j <= right; j++ {
			result = append(result, matrix[top][j])
		}
		top++ // 顶墙下移
		if len(result) == m*n {
			break // 提前终止：可能已经取完全部元素
		}

		// ── ② 向下：遍历 right 列，从 top → bottom ──
		for i := top; i <= bottom; i++ {
			result = append(result, matrix[i][right])
		}
		right-- // 右墙左移
		if len(result) == m*n {
			break
		}

		// ── ③ 向左：遍历 bottom 行，从 right → left ──
		// 注意：只有还有多于一行时才执行，否则会和第①步重复
		if top < bottom {
			for j := right; j >= left; j-- {
				result = append(result, matrix[bottom][j])
			}
			bottom-- // 底墙上移
		}

		// ── ④ 向上：遍历 left 列，从 bottom → top ──
		// 注意：只有还有多于的一列时才执行，否则会和第②步重复
		if left < right {
			for i := bottom; i >= top; i-- {
				result = append(result, matrix[i][left])
			}
			left++ // 左墙右移
		}
	}

	return result
}

[!success] ✅ 运行验证

这是 LeetCode 第 54 题，通过率约 62%，是一道经典的 边界收缩 面试题。

• 运行时间：约 0~7 ms（Go，击败 ~90%+ 提交）
• 空间消耗：O(1) 额外空间（不计返回值）
• 面试表现：很高。面试官最常追问的问题：
  • 为什么第③步需要 top < bottom 而第④步需要 left < right？（防止在退化为单行/单列时重复取值）
  • 为什么第①②步不需要额外的检查？（因为外层 len(result) < m*n 已经兜住了——不足时会由 break 截断）
  • len(result) == m*n 的 break 放在哪里最合适？（放在第①②步之后，因为这两步总是安全的；第③④步有自保护条件 top < bottom / left < right，break 可以放也可以不放）
  • 1×1 矩阵的情况？（第①步取一个元素后 length==m*n，break 退出，正确返回 [matrix[0][0]]）

[!quote] 💬 延伸思考

这道题的核心思维是 "将二维导航问题转化为一维约束"。与其纠结每个拐点的精确转向规则，不如关注：

四面墙在哪里？每走一步，哪面墙该推进？什么时候四面墙碰在一起？

这种建模方式可以把看似复杂的遍历逻辑简化为四个对称的循环。记住这个模板 「四边界 + 四步循环 + 重叠检查」，你可以快速解决螺旋相关的绝大多数变体题——包括打印螺旋矩阵、螺旋遍历、螺旋填充等。