LeetCode 每日一题解析54. Spiral Matrix 螺旋矩阵剥洋葱法与方向数组法全解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南基于本仓库「每日一题」系列文档 daily/2019-07-29.md 展开完整讲解 LeetCode 54 题「螺旋矩阵Spiral Matrix」的题目背景、两种经典解法的核心思想与 JavaScript 实现并结合仓库源码 daily/answers/54.spiral-matrix.js 给出第三种精简实现。读完本文你将掌握如何通过「边界收缩」与「方向数组」两种思路在 O(m×n) 时间内完成矩阵螺旋遍历并理解其时间复杂度与空间复杂度推导可直接迁移到旋转矩阵、蛇形遍历等同类题目。信息卡片题目LeetCode 54. Spiral Matrix螺旋矩阵分类标签Array数组、Matrix矩阵所属系列本仓库 每日一题 活动2019-07-29 期历史汇总中编号 54.Spiral Matrix核心考点边界收缩、方向模拟、循环终止条件设计题目描述给定一个包含 m × n 个元素的矩阵m 行 n 列请按照顺时针螺旋顺序返回矩阵中的所有元素。示例 1Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]示例 2Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7]从示例可以直观看到遍历顺序先沿第一行从左到右再沿最后一列从上到下然后沿最后一行从右到左再沿第一列从下到上……如此一圈一圈向内收缩直到所有元素被访问完毕。解法一剥洋葱法边界收缩这是最直观、最容易写对的思路原文档将其形象地称为「剥洋葱」——每一圈就像剥掉一层洋葱皮。核心思想一圈一轮row - col - row - col为一次完整的外圈遍历即“向右 → 向下 → 向左 → 向上”四个方向各走一段边界内收每完成一个方向的遍历对应的边界就向内收缩一步。row-col、col-row的切换都伴随读取起始位置的变化1 或 -1结束条件行头大于行尾rowT rowB或列左大于列右colL colR时说明矩阵已被剥完循环终止。以示例 1 的三行三列矩阵为例第一圈向右读[1,2,3]向下读[6,9]向左读[8,7]向上读[4]第二圈只剩中心元素[5]直接向右读入完成得到[1,2,3,6,9,8,7,4,5]。复杂度分析时间复杂度O(m × n)每个元素恰好被访问一次空间复杂度O(1)除结果数组外仅使用四个边界指针。参考实现JavaScript/** * param {number[][]} matrix * return {number[]} */ var spiralOrder function(matrix) { if(matrix.length 0) return []; let rowT 0; // 行顶 let rowB matrix.length - 1; // 行底 let colL 0; // 列左 let colR matrix[0].length - 1; // 列右 let result []; // 顺序是行、列、行、列每次切换读取的初始位置都会变化1(/- 1) while (colL colR rowT rowB) { for (let a colL; a colR; a) { result.push(matrix[rowT][a]); } rowT; for (let b rowT; b rowB; b) { result.push(matrix[b][colR]); } colR--; for (let c colR; c colL rowB rowT; c--) { result.push(matrix[rowB][c]); } rowB--; for (let d rowB; d rowT colR colL; d--) { result.push(matrix[d][colL]); } colL; } return result; };实现要点说明边界变量命名rowT行顶、rowB行底、colL列左、colR列右四次for循环分别对应四个方向每次遍历完成后立即把对应边界向中心收缩一步rowT、colR--、rowB--、colL循环条件colL colR rowT rowB保证了矩阵在只剩一行或一列时也能正确收尾——此时内层的向左、向上循环因边界条件rowB rowT、colR colL而自动跳过不会重复读取元素。解法二方向数组法单个 for 循环 方向切换剥洋葱法虽然直观但代码中有四个几乎对称的for循环略显冗长。原文档给出的第二种思路把四个方向统一抽象为方向向量用同一段循环代码完成全部遍历。核心思想四个方向可以用二维数组表示const dirs [[0, 1], [1, 0], [0, -1], [-1, 0]];分别对应right向右列 1、down向下行 1、left向左列 -1、up向上行 -1。四个方向分成两类水平方向right、left与垂直方向down、up。在两类方向上的最大移动步数分别是水平 n、垂直 m。遍历过程中每当方向切换就把对应类别的最大步数减一逐步缩小移动范围直到 n 0 或 m 0 表示所有元素遍历完毕。以文档中的 3 行 5 列矩阵为例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15对上面矩阵遍历时的操作序列为向右 5 次算上从左侧第一次进入向下 2 次向左 4 次向上 1 次向右 3 次向下 0 次 —— 结束可以看到水平方向right/left的移动极值从 n 开始逐轮递减垂直方向down/up的移动极值从 m-1 开始逐轮递减。两类方向各自的初始最大值是[n, m-1]当n 0 || m 0时元素已全部遍历完。这种写法的优点是把四个方向的遍历合并成一个for循环缺点是while循环轮次变多但整体时间复杂度不变。复杂度分析时间复杂度O(m × n)仍然是每个元素恰好访问一次空间复杂度O(1)。参考实现JavaScript/** * param {number[][]} matrix * return {number[]} * 一个for循环,但while变多了 */ var spiralOrder function(matrix) { if(matrix.length 0) return []; let m matrix.length; let n matrix[0].length; let result []; const dirs [[0, 1], [1, 0], [0, -1], [-1, 0]] // 控制方向的数组 // 元素坐标row,col; let row 0; let col -1; let steps [n, m-1] let dir 0; // 初始方向 while(steps[dir%2]) { for(let i 0; i steps[dir%2]; i) { // 方向的改变的效果row/col能增能减 row dirs[dir][0]; col dirs[dir][1]; result.push(matrix[row][col]) } steps[dir%2]--; // 移动极值缩小 dir (dir1)%4; // 方向改变 } return result; };实现要点说明初始坐标设为row 0, col -1目的是让第一步col 1恰好落在矩阵左上角matrix[0][0]steps[dir % 2]用方向的奇偶性区分水平与垂直dir 0right与dir 2left时dir % 2 0取水平步数 ndir 1down与dir 3up时取垂直步数 m-1每次方向切换后steps[dir % 2]--缩小对应类别的移动极值dir (dir 1) % 4让方向按 right → down → left → up → right 循环while(steps[dir % 2])在步数降为 0 时退出此时矩阵已遍历完毕。解法三仓库源码中的精简实现边遍历边判停除了原文档中的两种写法本仓库的每日一题答案文件 daily/answers/54.spiral-matrix.js 中保存了第三种实现。它在剥洋葱思想的基础上把循环条件改为while(true)在每完成一个方向的遍历后立即检查边界是否越界并break代码更紧凑var spiralOrder function(matrix) { const res []; if (matrix.length 0) return res; let top 0; let bottom matrix.length - 1; let left 0; let right matrix[0].length - 1; while (true) { for (let i left; i right; i) res.push(matrix[top][i]); top; if (top bottom) break; for (let i top; i bottom; i) res.push(matrix[i][right]); right--; if (left right) break; for (let i right; i left; i--) res.push(matrix[bottom][i]); bottom--; if (top bottom) break; for (let i bottom; i top; i--) res.push(matrix[i][left]); left; if (left right) break; } return res; };这个版本与解法一相比有三个不同点边界命名更简洁top/bottom/left/right循环条件改为while(true)退出完全依赖四个方向内的break判断每次边界收缩后立即检查top bottom或left right逻辑上更接近「剥完一层就判断是否结束」的自然直觉也不需要在反向遍历的for循环里追加额外边界条件。该文件头部保留了题解来源注释LeetCode 讨论区一篇名为 Clean Java readable human-friendly code 的帖子可供参考比对不同语言的同思路实现。其时间复杂度同样为 O(m × n)空间复杂度 O(1)。三种解法对比与选择建议对比维度解法一剥洋葱法解法二方向数组法解法三精简判停法核心思路四边界逐方向收缩方向向量 步数递减边界收缩 立即判停循环结构1 个 while 4 个 forwhile 单个 for轮次变多while(true) 4 个 for代码可读性高四个方向清晰对称中需要理解方向数组与步数递减高结构最紧凑出错风险点反向遍历需追加边界判断初始坐标与步数初值易错四个 break 位置必须准确时空复杂度O(m×n) / O(1)O(m×n) / O(1)O(m×n) / O(1)三种解法的时间复杂度、空间复杂度完全一致差异只体现在代码组织方式上面试首推解法一边界收缩思路与「剥洋葱」的直观比喻完全对应最不容易写错也最容易向面试官讲清逻辑解法二适合理解遍历本质方向数组把「方向」这一抽象概念具体化为数据对后续处理旋转矩阵、蛇形填数等问题有启发意义解法三适合追求简洁仓库源码中的实现已通过实战检验可作为日常刷题的参考范式。延伸与进阶螺旋遍历在矩阵类题目中属于基础操作掌握后可以进一步挑战旋转矩阵如 LeetCode 48. Rotate Image同样涉及边界收缩与坐标映射仓库中的题解 problems/48.rotate-image.md 与配套绘图 assets/drawio/48.rotate-image.drawio 可对照学习螺旋矩阵 IILeetCode 59把「读」改为「写」用同一套边界收缩逻辑反向填充矩阵检验对思路的掌握程度本仓库为本题维护了可视化绘图文件 assets/drawio/54.spiral-matrix.drawio可用 draw.io 打开查看螺旋遍历的边界变化过程辅助理解「剥洋葱」每一圈的收缩细节。小结本文围绕 LeetCode 54 题「螺旋矩阵」给出了三种 JavaScript 实现基于四边界收缩的剥洋葱法、基于方向数组的步数递减法以及仓库答案文件中保存的精简判停版。三者在时间复杂度 O(m×n) 与空间复杂度 O(1) 上保持一致区别仅在于循环组织方式。建议以「剥洋葱」思路作为首选模板配合方向数组理解遍历本质即可稳定应对螺旋遍历及其变体题目。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考