螺旋矩阵满分解法：方向数组与四边界收缩全解析

力扣hot100第19题螺旋矩阵第一次写的人大概率会经历这个流程看题觉得简单写起来也快提交却报错然后陷入“到底哪里没判断到”的自我怀疑。我当年也是这样样例一次过一提交就翻车后来才发现问题出在转向条件的顺序上。后面把这个题吃透了才发现它考察的东西其实特别基础就是二维数组的边界控制加循环不变量这也是为什么它被放进hot100当常客。这篇文章我会把螺旋矩阵的完整解题思路、两种能过的Python写法、以及我本地反复测试时踩过的边界坑一次性理清楚。适合正在准备面试、刷到hot100这个位置、或者想搞懂算法题里“方向控制”这类套路的读者。不需要你有特别深的算法底子只要会Python的基础语法、知道二维数组怎么取元素就能跟着走完。1. 题目倒是不长但螺旋路径里藏着三条硬规则1.1 题目到底让你干什么给定一个m x n的矩阵按顺时针螺旋顺序返回矩阵里的所有元素。举个最经典的例子matrix [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] # 输出[1, 2, 3, 6, 9, 8, 7, 4, 5]再举个非正方形的例子这个例子必须看因为很多人只拿正方形矩阵测试结果在非正方形上翻车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 拆解路径能得到三条硬规则第一条移动方向固定按顺序循环右、下、左、上每碰一次墙就换方向。第二条所谓“碰墙”包含两种情形。一是坐标越界比如已经在最右边还继续往右走二是下一个格子已经访问过了因为螺旋走到内圈时会反复经过已经被取走的格子附近。第三条结束条件不是“转了几圈”而是“已经取到了 m x n 个元素”。只要还没取够就得继续走取够了不管方向朝哪立刻停。这三条规则几乎就是全部题眼。任何解法本质上都逃不开这三点区别只在于用什么样的代码结构去表达它们。1.3 两个容易理解偏的点第一矩形不一定是正方形。题目明确给的是m x nm 和 n 可以不等。这意味着“剥洋葱”式收缩边界时不能假设上下左右四个边界一定同时存在。第二方向是顺时针但顺时针并不是“每次转90度”这么简单而是在当前方向走不通的时候才转否则就一直走。写代码时最容易犯的错就是“每走一步就转向”那样会得到一条蛇形轨迹不是螺旋。2. 解法一方向数组 已访问标记最接近“人肉走迷宫”的写法2.1 核心思路把“走迷宫”翻译成代码我最先推荐这个解法因为它和人的直觉最接近。你不需要一开始就抽象出“边界收缩”这种概念只需要模拟一个“人”在矩阵里走路的过程左手拿着一个方向列表按右、下、左、上循环切换每走一步先看一眼下一个位置能不能走能走就走不能走就右转方向再判断一次直到收集到全部元素这个思路的关键数据结构是两个方向数组和已访问数组。方向数组长这样directions [(0, 1), (1, 0), (0, -1), (-1, 0)]四个元组分别对应“行坐标的增量、列坐标的增量”。向右走列坐标加1向下走行坐标加1向左走列坐标减1向上走行坐标减1。这个顺序必须按照顺时针来不能乱排。已访问数组则是一个和原矩阵同等大小的布尔矩阵初始全是False。每访问一个格子就把对应的位置改成True。它的作用是当你走到内圈时靠它拦住你“回头走已访问的路”。2.2 完整代码与逐行解释def spiralOrder(matrix): if not matrix or not matrix[0]: return [] m, n len(matrix), len(matrix[0]) visited [[False] * n for _ in range(m)] directions [(0, 1), (1, 0), (0, -1), (-1, 0)] cur_dir 0 x, y 0, 0 result [] for _ in range(m * n): result.append(matrix[x][y]) visited[x][y] True nx x directions[cur_dir][0] ny y directions[cur_dir][1] if nx 0 or nx m or ny 0 or ny n or visited[nx][ny]: cur_dir (cur_dir 1) % 4 nx x directions[cur_dir][0] ny y directions[cur_dir][1] x, y nx, ny return result代码很短但每一行都有讲究。我拆开说if not matrix or not matrix[0]这一行同时处理了空矩阵[]和矩阵只有空行[[]]的情况。matrix[0]为空的矩阵意思是m虽然大于等于1但n 0没有元素可取。这一步不加后面访问matrix[0][0]就会直接崩。主循环写的是for _ in range(m * n)而不是while加条件。因为矩阵总共就m * n个元素我每次循环正好收集一个元素循环固定执行这么多次就一定能把全部元素取完不需要额外的结束判断。这是我更推荐用for而不是while的原因不容易写成死循环。visited[x][y] True必须在“取元素”之后立刻标记不能等到下一步再标记否则当螺旋走到拐弯点时可能会在同一个格子上重复取值。接下来是转向判断if nx 0 or nx m or ny 0 or ny n or visited[nx][ny]: cur_dir (cur_dir 1) % 4 nx x directions[cur_dir][0] ny y directions[cur_dir][1]这里要注意一个细节先计算nx, ny再判断它是否越界或已访问。如果判断为真说明当前方向走到头了需要换方向换方向后再重新计算nx, ny。为什么取模% 4因为方向数组长度是4索引只能取0到3取模就完成了“右→下→左→上→右”的循环切换。2.3 为什么转向条件要同时判断“越界”和“已访问”很多初学者只判断越界不判断已访问结果在非正方形矩阵上死循环。原因在于螺旋走到内圈的时候当前位置的下一个格子并不越界但已经被外层访问过了比如3x3矩阵走到(1,1)的正上方(0,1)时(0,1)是合法的坐标但已经在第一圈被取走。如果不判断visited[nx][ny]你就会一直往这个方向走然后绕回已经取过的路线上越走越乱。用一句话总结越界判断拦住“走到矩阵外面”已访问判断拦住“走到已经取过的区域”两者缺一不可。2.4 这段代码的优点和代价优点是思路直白照着人体直觉写出错的概率低面试时也容易给面试官讲清楚。代价是额外占用了一个m x n的布尔矩阵空间复杂度是O(mn)。对这道题来说这个空间开销其实不算大因为矩阵本身就有O(mn)个数据多一个同规模的布尔矩阵在典型面试题的限制下完全能接受。不过如果你追求更优雅、空间更省的写法就需要看下一种解法。3. 解法二四边界收缩法面试里更讨喜的简洁方案3.1 核心思路从“人走路”换成“剥洋葱”方向数组法站在“行走者”的视角四边界收缩法则站在“管理者”的视角。想象一个洋葱螺旋顺序就是从外到内一层层剥。每剥一层就处理掉当前最外圈的四条边然后把上下左右四个边界往里缩一圈继续处理剩下的内圈。这个过程不需要记录每个格子是否访问过因为边界收缩本身就保证了“已经处理过的区域不会再被碰到”。具体来说维护四个变量top当前还没处理区域的顶边行号初始为0bottom当前还没处理区域的底边行号初始为m - 1left当前还没处理区域的左边列号初始为0right当前还没处理区域的右边列号初始为n - 1每次循环按“上边从左到右、右边从上到下、下边从右到左、左边从下到上”的顺序把四条边全部收集一遍然后top 1、bottom - 1、left 1、right - 1继续下一圈。3.2 完整代码与逐行解释def spiralOrder(matrix): if not matrix or not matrix[0]: return [] top, bottom 0, len(matrix) - 1 left, right 0, len(matrix[0]) - 1 result [] while top bottom and left right: # 上边从左到右 for j in range(left, right 1): result.append(matrix[top][j]) top 1 # 右边从上到下 for i in range(top, bottom 1): result.append(matrix[i][right]) right - 1 # 下边从右到左 if top bottom: for j in range(right, left - 1, -1): result.append(matrix[bottom][j]) bottom - 1 # 左边从下到上 if left right: for i in range(bottom, top - 1, -1): result.append(matrix[i][left]) left 1 return result这段代码里有两个if是很多人容易忽略的关键。解释一下第一次循环结束时top已经加了1。如果矩阵只有一行此时top会大于bottom那第三段“下边从右到左”就不该执行因为该行已经被“上边”部分全部取过了再取就会重复。同理如果矩阵只有一列right已经减了1第四段“左边从下到上”也不该执行。所以这两个if实际上是“在非正方形矩阵下防止越界和重复取值”的保险丝。3.3 单行单列矩阵为什么能安全通过拿matrix [[1, 2, 3]]演示初始top0, bottom0, left0, right2第一次循环上边把1,2,3全部取完top变成1右边range(top, bottom1)即range(1, 1)空不执行下边因为top bottom是1 0为假跳过左边因为left right成立但range(bottom, top-1, -1)即range(0, 0, -1)空不执行第二次循环top bottom即1 0为假循环退出结果正确没有越界也没有重复。这就是两个if在起作用。再看matrix [[1], [2], [3]]初始top0, bottom2, left0, right0第一次循环上边取1top1右边取2,3right-1下边top bottom成立但range(right, left-1, -1)即range(-1, -1, -1)空不执行左边left right即0 -1为假跳过循环退出同样正确。所以这个写法天然适配各种非规则矩形不需要额外特判。3.4 空间复杂度的优势这个写法的额外空间只有四个整数变量top, bottom, left, right再加上结果数组result。结果数组是题目要求返回的不算额外空间。因此如果忽略输出数组额外空间复杂度是O(1)比方向数组法的O(mn)更有优势。在力扣的题目限制下两种解法都能通过时间复杂度都是O(mn)因为你无论如何都要遍历所有元素这是下界不可能是更小的复杂度。4. 两种写法的时间空间对比以及单行单列矩阵的特别测试4.1 直接对比对比维度方向数组法四边界收缩法时间复杂度O(mn)O(mn)额外空间复杂度O(mn)需要布尔矩阵O(1)只需要四个边界变量代码可读性直观接近人肉模拟简洁但两个if需要理解面试讲解难度容易讲明白需要把边界收缩逻辑讲透出错风险点转向顺序、visited判断时机两个if的缺失、循环条件写错4.2 空间差异到底来自哪里方向数组法的空间消耗在于它需要一个和原矩阵同等规模的visited矩阵。虽然布尔值在Python里也是对象实际内存开销比理论上大不少但leetcode通常不会因此卡你。真正值得思考的是为什么四边界法不需要visited因为边界收缩法把所有“已访问”信息压缩进了四个边界整数里。top以上的行全部处理完了bottom以下的行也全部处理完了left左边的列、right右边的列同理。所以只要看一眼四个变量的值就知道当前区域的轮廓根本不需要再逐格标记。这个思路值得记住很多矩阵遍历题都能用“边界变量压缩状态”的技巧比开一个同等大小的标记数组更节省空间。4.3 面试场景里我更推荐哪种如果面试官没有明确要求“空间O(1)”我建议你优先写四边界收缩法。理由有三点第一代码短手写不容易出错。第二它展现了“压缩状态”的思维面试官会觉得你不是在背代码而是真的理解遍历过程。第三力扣的模板题里螺旋矩阵最常见的最优解就是这个写法讨论起来有共识。但如果你在面试时比较紧张怕两个if忘记加先写方向数组法拿到正确结果再跟面试官说“我能优化成O(1)空间”也是一条很稳的路径。先保证有解再展示优化是面试里最稳妥的策略。补充一点我在本地测试时强烈建议把单行矩阵[[1,2,3]]、单列矩阵[[1],[2],[3]]、一行一列矩阵[[1]]、空矩阵[]、空行矩阵[[]]这五种情况全部跑一遍。很多LeetCode的隐藏测试用例就藏在其中自己提前验证过心里才有底。5. 实测最容易翻车的5个边界细节我的排查记录5.1 空矩阵和空行的处理顺序我第一次提交时写的是if len(matrix) 0结果遇到[[]]直接报错。原因是[[]]的len(matrix)等于1不为0能通过第一层检查但进入代码后访问matrix[0][0]时matrix[0]是空列表下标直接越界。后来我改成if not matrix or not matrix[0]一次性挡住两种情况。这个写法也是力扣题解区最常见的写法原因就在于它用两次not判断同时覆盖了“矩阵不存在”和“矩阵第一行不存在”两种边界。经验总结处理二维数组时matrix和matrix[0]是两个层面的存在性必须分开判断。这个问题我在其他矩阵类题目里也经常遇到几乎成了每次写矩阵题的第一道保险。5.2 方向数组法里visited更新位置放错了方向数组法有一个隐蔽的坑visited[x][y] True如果放在转向判断之后会导致什么结果模拟一下假设当前位置是(0,2)方向是右nx, ny是(0,3)越界了所以转向为下x, y更新为(1,2)。如果visited[0][2]还没被标记为True那么下一次到达这个格子附近时可能又判断它可访问导致同一个值被重复加入结果。正确的顺序是加入结果后立刻标记标记完再计算下一步。顺序上不能颠倒。5.3 四边界法忘记加两个if导致的重复元素这个坑我在前面的示例中已经演示过。大家可以试着删掉两个if跑一下matrix [[1,2,3]]会得到[1, 2, 3, 2, 1]这种带重复元素的错误结果。原因就是“下边”那段循环在top bottom时仍然执行了第二次把已经取完的那一行又从右往左取了一遍。这个问题的复现非常简单几乎每个学这个解法的人都会踩一次。踩过之后只要记得“每次处理完上边和右边之后要先判断区域是否还存在再处理下边和左边”就永远不会再犯。5.4 while循环条件写成top bottom and left right这是一个更隐蔽的写法。如果写成while top bottom and left right在3x3矩阵上第一次循环就会出问题。因为第一次循环结束后top1, bottom1, left1, right1此时top bottom且left right中心元素还没取但循环条件已经不满足了结果会漏掉最中心的5。正确的判断是while top bottom and left right等号必须带上。这是唯一的边界点中心位置仍然有元素可取不能提前退出。5.5 方向数组的取值顺序排错方向数组必须严格按右、下、左、上排列。如果我写成[(0,1), (0,-1), (1,0), (-1,0)]也就是“右、左、下、上”得到的路径就不是螺旋而是蛇形折返。这类错误在代码阅读时很难一眼看出因为语法完全合法必须靠运行结果才能暴露。我建议在写方向数组时在注释里标注“右、下、左、上”既能防止自己写错也能让阅读代码的人快速理解。6. 从螺旋矩阵到螺旋矩阵II一套方向控制思维的复用6.1 力扣第59题螺旋矩阵II的代码差异螺旋矩阵II和本题几乎完全相反本题给矩阵要你按顺序输出元素第59题给一个整数n要你生成一个n x n的矩阵按螺旋顺序填入1到n^2。如果掌握了四边界收缩法这道题只需要把“遍历取元素”换成“遍历填数字”def generateMatrix(n): matrix [[0] * n for _ in range(n)] top, bottom 0, n - 1 left, right 0, n - 1 num 1 while top bottom and left right: for j in range(left, right 1): matrix[top][j] num num 1 top 1 for i in range(top, bottom 1): matrix[i][right] num num 1 right - 1 if top bottom: for j in range(right, left - 1, -1): matrix[bottom][j] num num 1 bottom - 1 if left right: for i in range(bottom, top - 1, -1): matrix[i][left] num num 1 left 1 return matrix两者的结构几乎一模一样区别只是把result.append换成了matrix[坐标] num。6.2 方向控制思维还能用在哪些题上螺旋矩阵的核心思维是“按固定方向移动遇到边界或已访问就转向”这个套路在以下几类题里经常复用矩阵旋转如“旋转图像”本质上是按环来交换元素和螺旋的“逐层处理”异曲同工对角线遍历虽然方向规律不同但同样需要精确控制二维坐标的变化迷宫类问题如果题目允许“碰壁转向”方向数组是绕不开的基础工具蛇形填充用于填充矩阵时按“之”字形行走和螺旋矩阵一样需要方向切换我在实际刷题时发现一个规律矩阵类题目往往不是考你多复杂的算法而是考你对“坐标变化”和“边界条件”的敏感度。螺旋矩阵这题的价值就在于它把这两个基本功压到了极致题目本身虽然简单但真正能一次写对的人并不多。6.3 一个能通用的“方向控制”小模板如果你经常做矩阵遍历类题目可以在本地维护一套自己的方向模板# 方向右、下、左、上 directions [(0, 1), (1, 0), (0, -1), (-1, 0)] # 判断下一步是否可行 def can_move(nx, ny, m, n, visited): return 0 nx m and 0 ny n and not visited[nx][ny]把“判断可移动”独立成一个辅助函数可以让你在主循环里少想一件事注意力集中在业务逻辑上。我在写了几个矩阵遍历题之后就把这套模板固定了下来后续遇到类似题会省很多时间。我个人实际用下来的体会是螺旋矩阵这道题真正重要的不是记住某一种解法而是搞清楚“遍历顺序”和“边界条件”之间的耦合关系。方向数组法和四边界收缩法一个靠外部标记记住状态一个靠边界收缩压缩状态本质上是同一套常识的两种表达。你只要在纸上把3x3和3x4两个例子手动走一遍理解了路径是怎么拐弯的代码自然就能写对甚至还能自己推出更多变体。最后再分享一个小技巧平时刷这类矩阵题多准备几个非正方形的测试用例能帮你提前暴露大部分隐藏bug。