宿州市网站建设_网站建设公司_UI设计_seo优化

Java版LeetCode热题100之“螺旋矩阵”：从模拟到按层遍历的优雅解法

摘要：本文深入剖析 LeetCode 第 54 题 “螺旋矩阵”，全面覆盖原题回顾、算法构思、两种主流解法（方向模拟法与按层遍历法）、代码实现、复杂度分析、面试高频问答、实际应用场景及延伸思考。我们将从直观的路径模拟出发，逐步演进至满足O(1) 额外空间的最优解，并揭示其背后精妙的“边界收缩”思想，助你彻底掌握这一经典矩阵遍历难题。

一、原题回顾

题目名称：螺旋矩阵
题目编号：LeetCode 54
难度等级：中等（Medium）

题目描述

给你一个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. 边界处理：每走完一圈，边界向内收缩
2. 转向逻辑：何时从“向右”转为“向下”？
3. 终止条件：何时遍历完成？
4. 特殊形状：单行、单列、奇数/偶数维度

解题方向

有两种主流思路：

方法一：方向模拟（带 visited 数组）

• 维护当前方向（右、下、左、上）
• 使用visited数组记录已访问位置
• 遇到边界或已访问位置时转向

✅ 优点：逻辑直观，易于理解
❌ 缺点：空间 O(mn)

方法二：按层遍历（边界收缩）

• 将矩阵视为若干“同心矩形层”
• 每层按四边顺序遍历：上→右→下→左
• 遍历完一层后，收缩边界（left++, right–, top++, bottom–）

✅ 优点：空间 O(1)，效率高
❌ 缺点：边界条件稍复杂

💡 题目虽未明确要求空间限制，但方法二是更优解，也是面试官期望的答案。

三、答案构思

方法一：方向模拟法

核心思想：像机器人一样在矩阵中行走，遇到墙就右转。

数据结构：

• directions = {{0,1}, {1,0}, {0,-1}, {-1,0}}：右、下、左、上
• visited[m][n]：记录是否访问过
• (row, col)：当前位置
• directionIndex：当前方向索引

流程：

1. 从 (0,0) 开始，方向向右
2. 访问当前位置，标记为已访问
3. 计算下一步位置
4. 若越界或已访问，则转向（directionIndex++）
5. 移动到新位置
6. 重复直到访问所有元素

方法二：按层遍历法（推荐！）

核心思想：把矩阵看作洋葱，一层一层剥开。

定义边界：

• top：当前层上边界（行号）
• bottom：当前层下边界（行号）
• left：当前层左边界（列号）
• right：当前层右边界（列号）

每层遍历顺序：

1. 上边：从left到right（行=top）
2. 右边：从top+1到bottom（列=right）
3. 下边（若存在）：从right-1到left+1（行=bottom）
4. 左边（若存在）：从bottom到top+1（列=left）

⚠️ 注意：第3、4步需判断left < right && top < bottom，防止重复访问（如单行/单列）

收缩边界：

• left++; right--; top++; bottom--;
• 直到left > right || top > bottom

四、完整答案（Java 实现）

方法一：方向模拟法（O(mn) 空间）

importjava.util.*;classSolution{publicList<Integer>spiralOrder(int[][]matrix){List<Integer>order=newArrayList<>();if(matrix==null||matrix.length==0||matrix[0].length==0){returnorder;}introws=matrix.length;intcols=matrix[0].length;boolean[][]visited=newboolean[rows][cols];inttotal=rows*cols;// 方向：右、下、左、上int[][]directions={{0,1},{1,0},{0,-1},{-1,0}};intdirectionIndex=0;introw=0,col=0;for(inti=0;i<total;i++){order.add(matrix[row][col]);visited[row][col]=true;// 计算下一步intnextRow=row+directions[directionIndex][0];intnextCol=col+directions[directionIndex][1];// 判断是否需要转向if(nextRow<0||nextRow>=rows||nextCol<0||nextCol>=cols||visited[nextRow][nextCol]){directionIndex=(directionIndex+1)%4;}// 移动到新位置row+=directions[directionIndex][0];col+=directions[directionIndex][1];}returnorder;}}

方法二：按层遍历法（O(1) 空间，推荐！）

importjava.util.*;classSolution{publicList<Integer>spiralOrder(int[][]matrix){List<Integer>order=newArrayList<>();if(matrix==null||matrix.length==0||matrix[0].length==0){returnorder;}introws=matrix.length;intcols=matrix[0].length;intleft=0,right=cols-1;inttop=0,bottom=rows-1;while(left<=right&&top<=bottom){// 1. 上边：从左到右for(intcol=left;col<=right;col++){order.add(matrix[top][col]);}// 2. 右边：从上到下for(introw=top+1;row<=bottom;row++){order.add(matrix[row][right]);}// 3. 下边和左边：仅当存在内部区域时才遍历if(left<right&&top<bottom){// 3a. 下边：从右到左for(intcol=right-1;col>left;col--){order.add(matrix[bottom][col]);}// 3b. 左边：从下到上for(introw=bottom;row>top;row--){order.add(matrix[row][left]);}}// 收缩边界left++;right--;top++;bottom--;}returnorder;}}

✅强烈建议：面试时直接写方法二，并解释为何需要if (left < right && top < bottom)。

五、代码分析

方法一：方向模拟法详解

关键组件

• 方向数组：{{0,1}, {1,0}, {0,-1}, {-1,0}}对应右、下、左、上
• 转向条件：越界或已访问
• 终止条件：访问了total = m*n个元素

执行流程（以示例1为例）

matrix = [[1,2,3],[4,5,6],[7,8,9]]

最终结果：[1,2,3,6,9,8,7,4,5]✅

优点与缺点

• ✅ 逻辑清晰，易于调试
• ❌ 需要额外 O(mn) 空间存储 visited
• ❌ 每次都要检查 visited，有轻微性能开销

方法二：按层遍历法详解（重点！）

边界定义

• 初始：left=0, right=n-1, top=0, bottom=m-1
• 每层遍历后：left++, right--, top++, bottom--

四边遍历细节

1. 上边：for (col = left; col <= right; col++)

   • 包含左右端点
   • 行固定为top

2. 右边：for (row = top+1; row <= bottom; row++)

   • 从top+1开始（避免重复访问右上角）
   • 列固定为right

3. 下边：for (col = right-1; col > left; col--)

   • 从right-1到left+1（不包含端点）
   • 行固定为bottom
   • 条件：left < right && top < bottom

4. 左边：for (row = bottom; row > top; row--)

   • 从bottom到top+1（不包含端点）
   • 列固定为left
   • 条件：同上

🔑关键：第3、4步的条件防止在单行/单列时重复访问！

示例演示：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

第一层（left=0, right=3, top=0, bottom=2）：

• 上边：[1,2,3,4]
• 右边：[8,12]（从 row=1 到 2）
• 下边：[11,10,9]（col=2→1→0，但条件left<right && top<bottom成立）
• 左边：[5]（row=2→1，但只到 top+1=1）

收缩后：left=1, right=2, top=1, bottom=1

第二层（单行）：

• 上边：[6,7]
• 右边：无（row=top+1=2 > bottom=1）
• 下边/左边：跳过（因 top==bottom）

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

为什么需要if (left < right && top < bottom)？

考虑单行矩阵：[[1,2,3]]

• 若无此条件：
  • 上边：[1,2,3]
  • 右边：无（top+1=1 > bottom=0）
  • 下边：会执行！for (col=2-1=1; col>0; col--)→[2]（错误！）
  • 左边：for (row=0; row>0; ...)→ 无
• 结果：[1,2,3,2]❌

加条件后：

• left=0, right=2, top=0, bottom=0
• top == bottom→ 不满足top < bottom→ 跳过下边和左边
• 结果：[1,2,3]✅

六、时间复杂度与空间复杂度分析

详细分析

• 时间复杂度：

  • 两种方法都访问每个元素恰好一次
  • 总操作数 = m × n → O(mn)
  • 这是理论最优，因为必须读取所有元素

• 空间复杂度：

  • 方法一：需m×n的visited数组 → O(mn)
  • 方法二：仅用常数个变量（left, right, top, bottom）→ O(1)
  • 输出列表order不计入空间复杂度（题目要求返回它）

✅按层遍历法是时间和空间的双重最优解！

七、常见问题解答（FAQ）

Q1：为什么方法二中右边从top+1开始？

A：避免重复访问右上角元素。

• 上边已访问(top, right)
• 若右边从top开始，会再次访问它

Q2：下边和左边为什么是开区间（不包含端点）？

A：因为四个角已被上边和右边访问。

• 右上角：上边访问
• 右下角：右边访问
• 左下角：下边不应访问（留给左边？不！）
• 实际上，下边从right-1到left+1，左边从bottom到top+1
• 这样确保每个元素只访问一次

Q3：如何处理单列矩阵？

A：方法二天然支持！

• 例如：[[1],[2],[3]]
• 第一层：
  • 上边：[1]
  • 右边：[2,3]（col=0 固定，row=1→2）
  • 下边/左边：跳过（因 left==right）
• 结果：[1,2,3]✅

Q4：如果矩阵是 1x1 呢？

A：完美处理！

• 上边：访问唯一元素
• 右边：top+1=1 > bottom=0→ 跳过
• 下边/左边：跳过
• 结果正确 ✅

Q5：能否逆时针螺旋？

A：可以！只需调整遍历顺序：

• 左 → 下 → 右 → 上
• 或修改方向数组顺序

八、优化思路总结

工程建议：

• 永远优先选择按层遍历法
• 在代码中添加注释说明if (left < right && top < bottom)的必要性
• 单元测试覆盖单行、单列、1x1、2x2 等边界情况

九、数据结构与算法基础知识点回顾

1. 矩阵遍历模式

• 常规遍历：行优先、列优先
• 特殊遍历：
  • 螺旋遍历（本题）
  • 对角线遍历（LeetCode 1424）
  • Z字形遍历（LeetCode 6）
• 核心：理解坐标变化规律

2. 边界收缩（Boundary Shrinking）

• 思想：通过维护动态边界来简化问题
• 应用：
  • 螺旋矩阵
  • 旋转图像（LeetCode 48）
  • 有序矩阵查找（LeetCode 240）
• 技巧：用left/right/top/bottom四个变量表示当前有效区域

3. 循环不变式（Loop Invariant）

• 在按层遍历中，循环不变式为：
  • left <= right && top <= bottom时，当前层未遍历
  • 每次循环处理一层，并收缩边界
• 这保证了算法的正确性和终止性

4. 空间复杂度分析

• 输出空间不计入：这是算法分析的通用约定
• 原地算法：额外空间 O(1)
• 辅助空间：除输入输出外的空间使用

十、面试官提问环节（模拟对话）

Q：你的按层遍历法，如果去掉if (left < right && top < bottom)会怎样？

A：会导致重复访问，尤其在单行或单列矩阵中。

• 例如[[1,2,3]]会输出[1,2,3,2]
• 因为下边会从col=1到col>0，即访问matrix[0][1]=2再次
• 这个条件确保只有当存在“内部区域”时才遍历下边和左边

Q：能否用递归实现螺旋遍历？

A：可以，但不推荐。

voidspiral(int[][]mat,intl,intr,intt,intb,List<Integer>res){if(l>r||t>b)return;// 遍历当前层...spiral(mat,l+1,r-1,t+1,b-1,res);}

• 优点：代码简洁
• 缺点：递归深度 O(min(m,n))，可能栈溢出；空间不严格 O(1)

Q：如果矩阵非常大（如 10000x10000），你的解法会有性能问题吗？

A：时间复杂度 O(mn) 是最优的（必须访问每个元素）。

• 但可以考虑缓存友好性：按层遍历是行优先，对 CPU 缓存更友好
• 方向模拟法访问模式跳跃，缓存命中率低

Q：如何修改代码以支持逆时针螺旋？

A：只需调整遍历顺序：

// 逆时针：左 → 下 → 右 → 上for(introw=top;row<=bottom;row++)order.add(matrix[row][left]);// 左for(intcol=left+1;col<=right;col++)order.add(matrix[bottom][col]);// 下if(left<right&&top<bottom){for(introw=bottom-1;row>top;row--)order.add(matrix[row][right]);// 右for(intcol=right;col>left;col--)order.add(matrix[top][col]);// 上}

Q：你的解法能处理非矩形矩阵吗？

A：题目保证是矩形（m x n），但即使不是，只要matrix[i].length一致即可。

• 若每行长度不同，则需额外检查列边界，但本题无需考虑

十一、这道算法题在实际开发中的应用

虽然“螺旋矩阵”看似抽象，但其思想在多个领域有实际价值：

1. 图像处理与计算机视觉

• 螺旋扫描用于某些图像压缩算法
• 在目标检测中，从中心向外螺旋搜索可快速定位目标
• 纹理生成：按螺旋顺序填充像素可产生特殊视觉效果

2. 游戏开发

• 地图探索：玩家从中心开始螺旋探索未知区域
• 技能范围：某些技能影响螺旋区域内的敌人
• 迷宫生成：螺旋路径可作为迷宫的基础结构

3. 内存布局与缓存优化

• Z-order曲线（Morton码）是一种空间填充曲线，类似螺旋
• 用于数据库索引（如 GeoHash）、图像存储（提高局部性）
• 螺旋遍历的思想有助于理解空间局部性的重要性

4. 机器人路径规划

• 清洁机器人（如扫地机）常采用螺旋路径覆盖房间
• 无人机航拍：螺旋下降可均匀覆盖区域
• 本题算法可作为简单路径规划的原型

5. 数据可视化

• 螺旋图（Spiral Plot）用于展示周期性数据
• 在仪表盘中，螺旋布局可节省空间并增强视觉层次
• 按螺旋顺序渲染元素可产生动态效果

📌 核心价值：提供了一种高效的、具有空间局部性的遍历策略

十二、相关题目推荐

掌握本题后，可挑战以下变种或进阶题：

十三、总结与延伸

核心收获

1. 按层遍历是处理“同心结构”问题的强大工具
2. 边界收缩思想可简化复杂遍历逻辑
3. 条件判断（如left < right && top < bottom）对正确性至关重要
4. 空间优化往往比时间优化更有价值（O(1) vs O(mn)）

延伸思考

• 螺旋矩阵 III（LeetCode 885）：在无限网格中从 (r0,c0) 开始螺旋，直到访问 R×C 个格子

  • 需要动态扩展边界，更具挑战性

• 三维螺旋：如何在立方体中螺旋遍历？

  • 可分层处理，每层是二维螺旋
  • 或用方向向量 + 转向规则

• 非矩形螺旋：在六边形网格、极坐标系中如何螺旋？

  • 需要重新定义“方向”和“边界”

最后建议

• 面试时：直接写按层遍历法，清晰解释四边遍历逻辑
• 刷题时：手动模拟 2x2、3x3、1x4 等案例，验证边界条件
• 工程中：将螺旋遍历封装为工具函数，提高代码复用性

结语：“螺旋矩阵”是一道经典的矩阵遍历题，它不仅考察编码能力，更考验对边界条件的把控和空间思维的严谨性。掌握它，你不仅学会了一道题，更掌握了一种优雅处理“层次化结构”的通用范式。

愿你在算法征途中，如螺旋般层层深入，终达核心！🌀

字数统计：约 9200 字（含代码与表格）
适用读者：LeetCode 刷题者、Java 开发者、算法面试准备者
版权声明：本文为原创技术博客，转载请注明出处。