59. 螺旋矩阵II

题目

力扣题目

给你一个正整数 n，生成一个包含 1 到 n² 所有元素，并且元素按顺时针顺序螺旋排列的 n × n 正方形矩阵 matrix。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

对应矩阵：

1 2 3
8 9 4
7 6 5

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

考察内容

• 二维数组的创建与下标访问
• 顺时针遍历矩阵
• 四条边界的维护和收缩
• 循环不变量与边界条件
• 避免重复填写矩阵四个角

解题思路

这是一道典型的模拟题。使用四个变量表示当前还没有填写的矩形区域：

• top：上边界；
• bottom：下边界；
• left：左边界；
• right：右边界。

四条边界都属于当前待填区域，因此维护的是闭区间：

只要 top <= bottom && left <= right，待填区域就仍然存在。每一轮按照顺时针方向填写当前区域最外层的四条边：

1. 从左到右填写上边，完成后执行 top++；
2. 从上到下填写右边，完成后执行 right--；
3. 如果仍有未填写的行，从右到左填写下边，完成后执行 bottom--；
4. 如果仍有未填写的列，从下到上填写左边，完成后执行 left++。

每填写完一条边，就立即将对应边界向内收缩。这样下一条边从新的边界开始，可以避免同一个角被重复填写。

循环不变量是：

• 四条边界外的所有位置都已经按顺时针顺序填写完毕；
• 四条边界围成的区域尚未填写；
• num 始终是下一个需要写入矩阵的数字。

n = 3 的执行过程

初始边界为 top = 0、bottom = 2、left = 0、right = 2。

第一轮结束后，待填区域从整个 3 × 3 矩阵收缩为中心的 1 × 1 区域，下一轮写入 9 后结束。

• 时间复杂度：$O(n^2)$，矩阵中的每个位置恰好写入一次；
• 空间复杂度：$O(n^2)$，用于存放返回矩阵；除返回值外只使用 $O(1)$ 额外空间。

代码演示

std::vector<std::vector<int>> generateMatrix(int n) {
    std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));

    // 维护四条边的边界下标
    int top    = 0;
    int bottom = n - 1;
    int left   = 0;
    int right  = n - 1;

    int num = 1;  // n的计数 从0 - n^2
    while (top <= bottom && left <= right) {
        // top: left -> right
        for (int j = left; j <= right; ++j) {
            matrix[top][j] = num++;
        }
        ++top;

        // right: top -> bottom
        for (int i = top; i <= bottom; ++i) {
            matrix[i][bottom] = num++;
        }
        --right;

        // bottom: right -> left
        if (top <= bottom) {
            for (int j = right; j >= left; --j) {
                matrix[bottom][j] = num++;
            }
            --bottom;
        }

        // right: bottom -> top
        if (left <= right) {
            for (int i = bottom; i >= top; --i) {
                matrix[i][left] = num++;
            }
            ++left;
        }
    }
    return matrix;
}

易错点

• 四条边使用了不同的区间规则：当前代码的上下左右边界都属于待填区域，遍历条件需要统一使用闭区间。
• 填完一条边后忘记收缩边界：每条边完成后必须立刻更新对应边界，否则下一轮会重复填写。
• 四个方向顺序错误：顺时针顺序应为右、下、左、上，也就是上边、右边、下边、左边。
• 重复填写四个角：后续边应从已经收缩后的边界开始，而不是再次从上一条边的角落开始。
• 没有判断剩余行或列是否存在：填写下边前检查 top <= bottom，填写左边前检查 left <= right，可以避免中心行或中心列被重复处理。
• 行列下标写反：访问二维数组时使用 matrix[row][column]；纵向移动改变行下标，横向移动改变列下标。
• 计数起点错误：题目要求写入 1 到 n²，因此 num 应从 1 开始。

总结

螺旋矩阵的核心是维护一个不断向内收缩的矩形边界。每轮固定按照“上、右、下、左”的顺序填写外圈，并在完成一条边后收缩相应边界。

解决矩阵模拟题时，最重要的是先统一区间定义，再明确：

1. 每个方向遍历哪些下标；
2. 哪些角已经被上一条边处理；
3. 遍历完成后收缩哪条边界；
4. 进入下一方向前是否需要检查剩余区域。

相关题目

• 54. 螺旋矩阵
• 48. 旋转图像
• 73. 矩阵置零
• 885. 螺旋矩阵 III
• 2326. 螺旋矩阵 IV