yicong@algo:~/code/06-matrix$ cat 0054-spiral-matrix.cpp
54. 螺旋矩阵
// 思路
螺旋遍历可以从外往内"一层一层剥",维护四条边界: top —— 还没遍历的最上面一行 bottom —— 还没遍历的最下面一行 left —— 还没遍历的最左一列 right —— 还没遍历的最右一列 每一圈按固定顺序走四步,走完四条边界各向内收一格: ① 上边:从左到右 (top, left → right) ② 右边:从上到下 (top+1 → bottom, right) ③ 下边:从右到左 (bottom, right-1 → left) ④ 左边:从下到上 (bottom-1 → top+1, left) 当 top > bottom 或 left > right 时,说明所有元素都遍历完了,循环结束。 版本一:四边界收缩,额外空间 O(1),力扣进阶要求的标准答案。 版本二:方向数组 + visited 标记,充当"小人走路,撞墙就右转"。 思路更直白、更不容易写错边界,但要多 O(m·n) 的 visited 空间。 它的价值在于:完全可以当作版本一的独立对照实现来验证正确性。
// 时间复杂度
O(m·n)。每个元素恰好被访问一次,m 是行数,n 是列数。
// 空间复杂度
版本一:O(1)(不计返回值 ans),只用了四个边界变量 版本二:O(m·n),需要 visited 数组
// 易错点
1. 第三步(下边)和第四步(左边)都必须各自再判一次边界: 第三步前面加 if (top <= bottom) 第四步前面加 if (left <= right) 不判的话,最后一圈只剩一行或一列时会重复遍历。 举例:1 行 3 列 [1,2,3],第一步已经把三个数收完了, 此时 top=1 > bottom=0,但如果不判,第三步还会从右往左再走一遍,把 2、1 重复加进去。 2. 四条边界的收缩别写错: 第一步扫完 top++,第二步扫完 right--,第三步扫完 bottom--,第四步扫完 left++。 3. 第二、三、四步的起点已经错开一格(top+1、right-1、bottom-1), 因为角上的元素在上一./上一步已经收过了,这里不能重复。 4. 空矩阵 matrix = [] 要能返回空数组。matrix[0] 只有在 rows > 0 时访问才安全。 5. 自检:答案长度必须恰好等于 rows * cols,不相等说明边界写错了。
// 面试口述要点
1. 先说本质:一圈一圈从外往里剥,四条边界向内收缩; 2. 讲清"四步 + 两次额外边界判断"的结构,主动点出最后一圈退化成一个点/一行/一列的坑; 3. 复杂度:时间 O(m·n)(每个格子进一次),空间 O(1)(不计返回值); 4. 如果被问"还有别的写法吗",给方向数组 + visited 模拟: 撞到越界或已访问就右转,代码更短更直观,但空间 O(m·n); 5. 顺带提一句自检手段:答案长度必须等于 m*n。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:四条边界收缩,额外空间 O(1)
// ================================================================
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
int rows = (int)matrix.size();
if (rows == 0) {
return ans; // 空矩阵
}
int cols = (int)matrix[0].size();
int top = 0; // 上边界(含)
int bottom = rows - 1; // 下边界(含)
int left = 0; // 左边界(含)
int right = cols - 1; // 右边界(含)
while (top <= bottom && left <= right) {
// ---------- ① 上边:从左到右 ----------
for (int j = left; j <= right; j++) {
ans.push_back(matrix[top][j]);
}
top++; // 这一行收完了,上边界下移
// ---------- ② 右边:从上到下 ----------
// 起点是 top+1,因为右上角那个元素在第一步已经收过了
for (int i = top; i <= bottom; i++) {
ans.push_back(matrix[i][right]);
}
right--; // 这一列收完了,右边界左移
// ---------- ③ 下边:从右到左 ----------
// 必须先判:如果上边界已经越过下边界,说明这一圈只剩一行,
// 而这一行在第一步就收完了,再走一遍就会重复
if (top <= bottom) {
// 起点是 right-1,因为右下角那个元素在第二步已经收过了
for (int j = right; j >= left; j--) {
ans.push_back(matrix[bottom][j]);
}
bottom--; // 这一行收完了,下边界上移
}
// ---------- ④ 左边:从下到上 ----------
// 同理,必须先判:如果左边界已经越过右边界,说明这一圈只剩一列,
// 而这一列在第二步就收完了,再走一遍就会重复
if (left <= right) {
// 起点是 bottom-1,因为左下角那个元素在第三步已经收过了
for (int i = bottom; i >= top; i--) {
ans.push_back(matrix[i][left]);
}
left++; // 这一列收完了,左边界右移
}
}
return ans;
}
// ================================================================
// 版本二:方向数组 + visited 标记,"撞墙就右转",O(m·n) 空间
// 方向顺序固定为 右 → 下 → 左 → 上,撞到边界或已访问就转 90°
// ================================================================
vector<int> spiralOrder_v2(vector<vector<int>>& matrix) {
vector<int> ans;
int rows = (int)matrix.size();
if (rows == 0) {
return ans;
}
int cols = (int)matrix[0].size();
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
// 右、下、左、上 —— 顺时针转 90° 就是 dir = (dir + 1) % 4
int dr[4] = {0, 1, 0, -1}; // 行增量
int dc[4] = {1, 0, -1, 0}; // 列增量
int dir = 0; // 当前朝向
int r = 0, c = 0; // 当前所在格子
for (int step = 0; step < rows * cols; step++) {
ans.push_back(matrix[r][c]);
visited[r][c] = true;
int nr = r + dr[dir];
int nc = c + dc[dir];
// 下一个格子越界或者已经走过 → 右转
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) {
dir = (dir + 1) % 4;
nr = r + dr[dir];
nc = c + dc[dir];
}
r = nr;
c = nc;
}
return ans;
}
};
// 本地测试:先读行数 r、列数 c,再读 r*c 个元素(按行);输出螺旋顺序数组
// 同时跑两个版本并比对结果,两个实现思路完全独立,适合互相验证
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int r, c;
if (!(cin >> r >> c)) return 0;
vector<vector<int>> matrix(r, vector<int>(c));
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
cin >> matrix[i][j];
vector<int> ans1 = Solution().spiralOrder(matrix);
vector<int> ans2 = Solution().spiralOrder_v2(matrix);
if (ans1 != ans2) {
cout << "MISMATCH\norig:";
for (int i = 0; i < r; ++i) {
cout << " [";
for (int j = 0; j < c; ++j) cout << matrix[i][j] << (j + 1 == c ? "" : ",");
cout << "]";
}
cout << "\nv1:";
for (int x : ans1) cout << ' ' << x;
cout << "\nv2:";
for (int x : ans2) cout << ' ' << x;
cout << '\n';
return 0;
}
if (ans1.empty()) {
cout << "none\n";
} else {
for (size_t i = 0; i < ans1.size(); ++i)
cout << ans1[i] << (i + 1 == ans1.size() ? '\n' : ' ');
}
return 0;
}