LeetCode-Go 题解 54. Spiral Matrix：螺旋矩阵的 Go 实现与两种解法源码剖析

LeetCode-Go 题解 54. Spiral Matrix螺旋矩阵的 Go 实现与两种解法源码剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode-Go 开源仓库中 54. Spiral Matrix 题解文档 为主体结合仓库内完整 Go 源码与测试用例深入剖析按顺时针螺旋顺序遍历 m x n 矩阵这一经典模拟题的两种实现思路方向状态机 访问标记法以及四边界逐圈收缩法。读完本文你将掌握螺旋遍历的边界条件处理技巧、Go 语言中两种写法的复杂度差异以及如何在当前仓库中直接运行测试进行验证。题目回顾什么是螺旋顺序题目原文对应 题解文档Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.即给定一个包含m x n个元素的矩阵m 行n 列请按照顺时针螺旋顺序返回矩阵中的所有元素。示例 1输入 [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出[1,2,3,6,9,8,7,4,5]遍历路径为顶行从左到右1→2→3→ 右列从上到下6→9→ 底行从右到左8→7→ 左列从下到上4→ 回到中心5。示例 2输入 [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出[1,2,3,4,8,12,11,10,9,5,6,7]这是一个 3 行 4 列的矩阵螺旋遍历依次走完外层一圈再进入内层剩余的第 2 行第 2~3 列最终得到如上输出。题目大意给定一个包含m x n个元素的矩阵m 行n 列按照顺时针螺旋顺序返回矩阵中的所有元素。这是一道典型的纯模拟题核心难点不在于算法思想而在于边界条件的处理二维数组会退化成一维单行、一列单列、甚至单个元素还有空矩阵的情况这些退化情形必须在代码中逐一考虑。解题思路总览仓库在 54. Spiral Matrix.go 中给出了两种完全不同的实现分别对应题解文档中提到的解法一与解法二方案核心思想时间复杂度额外空间复杂度解法一spiralOrder方向状态机 访问标记数组O(m × n)O(m × n)解法二spiralOrder2上/下/左/右四边界逐圈收缩O(m × n)O(1)除结果数组外两种方案都保证每个元素恰好被访问一次因此时间复杂度均为 O(m × n)。区别在于解法一用额外的visit矩阵记录已访问位置来判断何时转向而解法二通过收缩边界隐式保证不重复访问因此可以省掉标记数组。解法一方向状态机 访问标记数组源码逐段解析解法一的核心代码如下节选自 54. Spiral Matrix.go// 解法 1 func spiralOrder(matrix [][]int) []int { if len(matrix) 0 { return []int{} } res : []int{} if len(matrix) 1 { for i : 0; i len(matrix[0]); i { res append(res, matrix[0][i]) } return res } if len(matrix[0]) 1 { for i : 0; i len(matrix); i { res append(res, matrix[i][0]) } return res } visit, m, n, round, x, y, spDir : make([][]int, len(matrix)), len(matrix), len(matrix[0]), 0, 0, 0, [][]int{ {0, 1}, // 朝右 {1, 0}, // 朝下 {0, -1}, // 朝左 {-1, 0}, // 朝上 } for i : 0; i m; i { visit[i] make([]int, n) } visit[x][y] 1 res append(res, matrix[x][y]) for i : 0; i m*n; i { x spDir[round%4][0] y spDir[round%4][1] if (x 0 y n-1) || (x m-1 y n-1) || (y 0 x m-1) { round } if visit[x][y] 0 { visit[x][y] 1 res append(res, matrix[x][y]) } switch round % 4 { case 0: if y1 n-1 visit[x][y1] 1 { round continue } case 1: if x1 m-1 visit[x1][y] 1 { round continue } case 2: if y-1 0 visit[x][y-1] 1 { round continue } case 3: if x-1 0 visit[x-1][y] 1 { round continue } } } return res }关键设计点退化情形前置处理函数开头依次处理了三种退化情况——空矩阵len(matrix) 0、单行矩阵横向直接输出、单列矩阵纵向直接输出。这正是题解文档强调的需要注意特殊情况比如二维数组退化成一维或者一列或者一个元素。方向状态机spDir用长度为 4 的方向向量数组表示右→下→左→上四个方向round % 4取模得到当前方向。round每转一次弯就自增 1实现方向的循环切换。visit 标记数组visit[x][y]记录位置是否已被访问。主循环for i : 0; i m*n; i中每步先按当前方向前进到新位置若该位置未被访问则输出随后用switch round % 4检查当前方向的下一个格子是否已经被访问若是则转弯round从而保证始终贴着已访问区域的边缘前进。转弯的辅助判断if (x 0 y n-1) || (x m-1 y n-1) || (y 0 x m-1)这一行用于在到达矩阵四个角落时提前切换方向避免在角点出现方向错乱。这里的三个条件分别对应右上角右下角左下角三个必经转角。该方案的优点是思路直观、不容易漏格子缺点是visit标记数组额外占用了 O(m × n) 的空间。解法二四边界逐圈收缩源码逐段解析解法二的核心思想是维护top / bottom / left / right四个指针表示当前还未遍历的矩形区域每遍历完最外一圈就把四个边界向内收缩一格直到所有元素都被输出count sum。代码如下节选自同一文件// 解法 2 func spiralOrder2(matrix [][]int) []int { m : len(matrix) if m 0 { return nil } n : len(matrix[0]) if n 0 { return nil } // top、left、right、bottom 分别是剩余区域的上、左、右、下的下标 top, left, bottom, right : 0, 0, m-1, n-1 count, sum : 0, m*n res : []int{} // 外层循环每次遍历一圈 for count sum { i, j : top, left for j right count sum { res append(res, matrix[i][j]) count j } i, j top1, right for i bottom count sum { res append(res, matrix[i][j]) count i } i, j bottom, right-1 for j left count sum { res append(res, matrix[i][j]) count j-- } i, j bottom-1, left for i top count sum { res append(res, matrix[i][j]) count i-- } // 进入到下一层 top, left, bottom, right top1, left1, bottom-1, right-1 } return res }关键设计点提前算好元素总数count, sum : 0, m*n外层循环以count sum为停止条件。这正是题解文档中解法二提前算出一共多少个元素一圈一圈地遍历矩阵停止条件就是遍历了所有元素count sum的代码落地。四条边分四段输出每一圈拆成四条边分别遍历——顶边i top从left到right自左向右右边j right从top1到bottom自上向下起点top1避免重复输出右上角底边i bottom从right-1到left自右向左起点right-1避免重复输出右下角左边j left从bottom-1到top1自下向上条件i top避免重复输出左下角也避免单行/单列时重复输出左上角。每条内层循环都带count sum守卫这是应对退化矩阵的关键。例如在 3 x 4 这类宽大于高的矩阵中遍历到内层时底边可能与顶边重叠count sum守卫能防止越界重复输出。边界收缩一圈结束后执行top, left, bottom, right top1, left1, bottom-1, right-1将未遍历区域缩小到内层一圈循环往复。该方案无需任何标记数组除输出结果外仅使用常数个变量空间复杂度为 O(1)是面试中更推荐书写的版本。边界情况与测试用例验证仓库在 54. Spiral Matrix_test.go 中为上述两个函数编写了完整的表驱动测试Test_Problem54覆盖了本题绝大部分退化与常规场景测试输入期望输出覆盖场景[][]int{}[]int{}空矩阵[][]int{{}}[]int{}空行矩阵[][]int{{3}, {2}}[]int{3, 2}单列矩阵2 行 1 列[][]int{{2, 3}}[]int{2, 3}单行矩阵1 行 2 列[][]int{{1}}[]int{1}单个元素3 x 3 矩阵示例 1[1,2,3,6,9,8,7,4,5]奇数阶方阵3 x 4 矩阵示例 2[1,2,3,4,8,12,11,10,9,5,6,7]宽大于高的非方阵4 x 4 矩阵[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]偶数阶方阵测试代码对每个用例同时断言spiralOrder与spiralOrder2两个实现任一函数输出与期望不一致都会通过t.Fatalf立即失败got : spiralOrder(p.one) // ... got2 : spiralOrder2(p.one) if len(got2) ! len(a.one) { t.Fatalf(spiralOrder2(%v) %v, want %v, p.one, got2, a.one) } for i : range a.one { if got2[i] ! a.one[i] { t.Fatalf(spiralOrder2(%v) %v, want %v, p.one, got2, a.one) } }这组用例的完备性恰好印证了题解文档的提醒只要把退化情况处理妥当这道题基本可以一次通过。在仓库中运行与验证当前仓库以 Go module 管理依赖模块声明于 go.modGo 版本要求为 1.19。你可以直接在本地验证本题两种实现# 运行 0054 题单测含全部边界用例 go test -v ./leetcode/0054.Spiral-Matrix/如需统计整个题解仓库的测试覆盖率仓库提供了现成脚本 gotest.sh它会以atomic覆盖模式对./leetcode/...下的全部题目生成单一、合法的覆盖率文件# 生成覆盖率文件 coverage.txt bash gotest.sh该脚本会在仓库根目录产出coverage.txt配合仓库声明中100% test coverage的质量目标可作为你为仓库贡献新题解、或修改现有实现后回归验证的基准。小结螺旋矩阵是一道思路简单、细节繁多的模拟题。通过 LeetCode-Go 仓库中 54. Spiral Matrix 题解文档 与其两份源码实现可以清晰对比两种经典套路解法一方向状态机 visit 标记思维负担小依靠标记数组天然免疫重复访问适合快速写出正确解代价是 O(m × n) 的额外空间解法二四边界收缩空间最优O(1)通过count sum作为全局停止条件、四条边各自带count sum守卫来优雅应对各种退化矩阵是更值得在面试与工程中采用的写法。两者的正确性均由 54. Spiral Matrix_test.go 中的 8 组表驱动用例背书。理解这两份实现也就掌握了处理一切按轨迹遍历矩阵类题目如螺旋矩阵 II、旋转图像等的通用方法论。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考