目录
螺旋矩阵
题目描述
给你一个 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)向上：从下边界到上边界，遍历左边界列
(5)每次遍历完一个方向后，相应收缩边界
C++ 代码实现
#include <vector>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return {};
}
int m = matrix.size(), n = matrix[0].size();
vector<int> result;
// 定义四个边界
int top = 0, bottom = m - 1;
int left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// 1. 向右遍历上边界
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
top++; // 上边界下移
// 2. 向下遍历右边界
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][right]);
}
right--; // 右边界左移
// 3. 向左遍历下边界（如果还有行）
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.push_back(matrix[bottom][col]);
}
bottom--; // 下边界上移
}
// 4. 向上遍历左边界（如果还有列）
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.push_back(matrix[row][left]);
}
left++; // 左边界右移
}
}
return result;
}
};
复杂度分析
时间复杂度： O(m×n)
空间复杂度： O(1)（不计算结果数组）
方法二：方向向量法
核心思想
使用方向向量控制移动方向，遇到边界或已访问元素时转向。
算法步骤
(1)定义四个方向：右、下、左、上
(2)使用visited数组标记已访问元素
(3)当前方向无法继续时，按顺时针转向
C++ 代码实现
#include <vector>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return {};
}
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<int> result;
// 方向向量：右、下、左、上
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int direction_idx = 0;
int row = 0, col = 0;
for (int i = 0; i < m * n; i++) {
result.push_back(matrix[row][col]);
visited[row][col] = true;
// 计算下一个位置
int dr = directions[direction_idx].first;
int dc = directions[direction_idx].second;
int next_row = row + dr;
int next_col = col + dc;
// 检查是否需要转向
if (next_row < 0 || next_row >= m ||
next_col < 0 || next_col >= n ||
visited[next_row][next_col]) {
// 转向
direction_idx = (direction_idx + 1) % 4;
dr = directions[direction_idx].first;
dc = directions[direction_idx].second;
next_row = row + dr;
next_col = col + dc;
}
row = next_row;
col = next_col;
}
return result;
}
};
复杂度分析
时间复杂度： O(m×n)
空间复杂度： O(m×n)（visited数组）
方法三：递归法
核心思想
递归法的核心思想是分层处理：
(1)处理最外层的一圈元素
(2)递归处理内层子矩阵
(2)将结果合并
这种方法将复杂的螺旋遍历问题分解为：外圈遍历 + 内圈递归
C++ 代码实现
#include <vector>
using namespace std;
class Solution {
private:
// 递归函数：处理指定边界内的螺旋遍历
vector<int> spiral_recursive(vector<vector<int>>& matrix,
int top, int bottom, int left, int right) {
// 递归终止条件：无效边界
if (top > bottom || left > right) {
return {};
}
vector<int> result;
// 特殊情况1：只有一行
if (top == bottom) {
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
return result;
}
// 特殊情况2：只有一列
if (left == right) {
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][left]);
}
return result;
}
// 一般情况：遍历完整的外圈
// 1. 上边界：从左到右（不包括右上角，避免重复）
for (int col = left; col < right; col++) {
result.push_back(matrix[top][col]);
}
// 2. 右边界：从上到下（不包括右下角，避免重复）
for (int row = top; row < bottom; row++) {
result.push_back(matrix[row][right]);
}
// 3. 下边界：从右到左（不包括左下角，避免重复）
for (int col = right; col > left; col--) {
result.push_back(matrix[bottom][col]);
}
// 4. 左边界：从下到上（不包括左上角，避免重复）
for (int row = bottom; row > top; row--) {
result.push_back(matrix[row][left]);
}
// 递归处理内圈：边界各缩小1
vector<int> inner = spiral_recursive(matrix, top + 1, bottom - 1,
left + 1, right - 1);
// 合并外圈和内圈结果
result.insert(result.end(), inner.begin(), inner.end());
return result;
}
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return {};
}
int m = matrix.size(), n = matrix[0].size();
return spiral_recursive(matrix, 0, m - 1, 0, n - 1);
}
};
复杂度分析
时间复杂度：O(m×n)
每个元素只被访问一次 递归层数最多为 min(m,n)/2 总的元素访问次数为 m×n
空间复杂度：O(min(m,n))
递归栈深度为矩阵的层数：⌈min(m,n)/2⌉ 每层递归需要常数空间 不计算结果数组的话，空间复杂度为递归栈的深度
方法四：层次遍历法
核心思想
将矩阵看作多个同心矩形层，从外层到内层逐层遍历。
C++ 代码实现
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return {};
}
int m = matrix.size(), n = matrix[0].size();
vector<int> result;
// 计算层数
int layers = (min(m, n) + 1) / 2;
for (int layer = 0; layer < layers; layer++) {
// 当前层的边界
int top = layer, bottom = m - 1 - layer;
int left = layer, right = n - 1 - layer;
if (top > bottom || left > right) {
break;
}
// 特殊情况：只有一行或一列
if (top == bottom) {
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
} else if (left == right) {
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][left]);
}
} else {
// 正常的一圈
// 上边界
for (int col = left; col < right; col++) {
result.push_back(matrix[top][col]);
}
// 右边界
for (int row = top; row < bottom; row++) {
result.push_back(matrix[row][right]);
}
// 下边界
for (int col = right; col > left; col--) {
result.push_back(matrix[bottom][col]);
}
// 左边界
for (int row = bottom; row > top; row--) {
result.push_back(matrix[row][left]);
}
}
}
return result;
}
};
复杂度分析
时间复杂度： O(m×n)
空间复杂度： O(1)（不计算结果数组）
螺旋矩阵四种方法全面对比总结
方法概览对比
| 方法 | 时间复杂度 | 空间复杂度 | 核心思想 | 难度 | 推荐度 |
|---|---|---|---|---|---|
| 边界收缩法 | O(m×n) | O(1) | 维护四个边界，逐步收缩 | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| 方向向量法 | O(m×n) | O(m×n) | 模拟移动，遇障碍转向 | ⭐⭐ | ⭐⭐⭐ |
| 递归法 | O(m×n) | O(min(m,n)) | 外圈+内圈分层处理 | ⭐⭐⭐⭐ | ⭐⭐ |
| 层次遍历法 | O(m×n) | O(1) | 按层遍历，从外到内 | ⭐⭐⭐ | ⭐⭐⭐⭐ |
详细分析对比
1. 边界收缩法 ⭐⭐⭐⭐⭐ (最推荐)
核心思想
维护四个边界：top, bottom, left, right
按螺旋方向遍历：右→下→左→上
每完成一个方向，收缩对应边界
优势
- ✅ 空间效率最高：O(1)空间复杂度
- ✅ 逻辑直观：边界概念清晰易懂
- ✅ 代码简洁：循环结构简单
- ✅ 面试标准解法：被广泛认可
劣势
- ❌ 边界条件复杂：需要仔细处理边界收缩时机
- ❌ 调试稍难：边界错误不易发现
适用场景
- 面试首选方案
- 对空间要求严格的场景
- 需要高效稳定解法的生产环境
// 关键代码片段
while (top <= bottom && left <= right) {
// 右→下→左→上，每次遍历后收缩边界
for (int col = left; col <= right; col++)
result.push_back(matrix[top][col]);
top++;
// ... 其他三个方向
}
2. 方向向量法 ⭐⭐⭐ (学习友好)
核心思想
定义方向向量：{右, 下, 左, 上}
模拟螺旋移动，遇到边界或已访问元素时转向
使用visited数组标记访问状态
优势
- ✅ 最易理解：直接模拟螺旋移动过程
- ✅ 逻辑自然：符合人类思维方式
- ✅ 易于扩展：可以轻松改变移动方向
- ✅ 调试友好：每步移动都清晰可见
劣势
- ❌ 空间开销大：需要O(m×n)的visited数组
- ❌ 性能略差：每步都要检查多个条件
适用场景
- 学习算法时的理解工具
- 需要可视化过程的场景
- 对空间要求不严格的情况
// 关键代码片段
vector<pair<int, int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
// 检查转向条件：越界或已访问
if (next_row < 0 || next_row >= m || visited[next_row][next_col]) {
direction_idx = (direction_idx + 1) % 4;
}
3. 递归法 ⭐⭐ (思维训练)
核心思想
分治思想：外圈遍历 + 内圈递归
递归处理每一层，最终合并结果
边界参数：top, bottom, left, right
优势
- ✅ 思路最清晰：分层思维符合人类直觉
- ✅ 代码结构好：递归天然的分解结构
- ✅ 易于理解：问题分解明确
- ✅ 展示算法思维：体现分治思想
劣势
- ❌ 空间开销：递归栈深度O(min(m,n))
- ❌ 性能开销：函数调用成本
- ❌ 栈溢出风险：大矩阵可能导致栈溢出
- ❌ 复杂边界处理：需要处理单行单列情况
适用场景
- 算法思维训练
- 面试中展示分治思想
- 小规模数据处理
// 关键代码片段
vector<int> spiral_recursive(matrix, top, bottom, left, right) {
// 处理外圈 + 递归内圈
// 外圈：上→右→下→左
// 递归：spiral_recursive(top+1, bottom-1, left+1, right-1)
}
4. 层次遍历法 ⭐⭐⭐⭐ (工程实用)
核心思想
将矩阵看作多个同心矩形层
计算总层数：(min(m,n) + 1) / 2
从外层到内层逐层遍历
优势
- ✅ 空间效率高：O(1)空间复杂度
- ✅ 思路清晰：层次概念明确
- ✅ 易于优化：可以并行处理不同层
- ✅ 工程友好：代码结构规整
劣势
- ❌ 代码稍复杂：需要处理多种边界情况
- ❌ 层数计算：需要正确理解层数概念
适用场景
- 工程项目中的实现
- 需要处理大规模矩阵的场景
- 对代码结构有要求的项目
// 关键代码片段
int layers = (min(m, n) + 1) / 2;
for (int layer = 0; layer < layers; layer++) {
// 计算当前层边界
// 处理特殊情况：单行或单列
// 遍历完整一圈
}
面试策略建议
一面/基础面试
推荐：边界收缩法
- 先说思路，再写代码
- 重点展示边界处理能力
- 时间复杂度和空间复杂度分析
二面/深度面试
推荐：边界收缩法 + 其他方法对比
- 主要实现边界收缩法
- 简述其他方法的优劣
- 展示算法设计思维
算法专场面试
推荐：多方法展示
- 快速实现边界收缩法
- 详细解释递归法思路
- 分析各方法的适用场景
学习路径建议
阶段1：理解螺旋遍历本质
- 先学方向向量法 - 最直观易懂
- 手工模拟几个小例子
- 理解螺旋移动的规律
阶段2：掌握标准解法
- 重点学习边界收缩法
- 练习边界条件处理
- 熟练写出bug-free代码
阶段3：拓展算法思维
- 学习递归法 - 培养分治思维
- 理解层次遍历法 - 工程思维
- 对比各方法优劣
实际开发建议
生产环境首选
边界收缩法 - 空间效率高，性能稳定
学习和教学首选
方向向量法 - 最容易理解和实现
算法面试首选
边界收缩法 + 能够解释其他方法
大数据处理
层次遍历法 - 结构清晰，易于优化