yicong@algo: ~/code/06-matrix/0054-spiral-matrix.cpp

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;
}