59. 螺旋矩阵 II

1. 题目简介

难度：中等，原题链接：59. 螺旋矩阵 II。

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

2. 问题分析

从左上角开始，按右、下、左、上的顺序依次填入 1 到 n²。这与 54. 螺旋矩阵的行走规则相同，只是每到一个格子时，改为写入数字。

用 (i, j) 保存当前位置，t 保存方向，cur 保存下一个待填数字。每次把 cur 写入 res[i][j] 后，让 cur 加一，并用 walked[i][j] 标记这个格子已经填过。

移动前先检查下一步：如果越界或格子已经填过，就顺时针转向。例如 n = 2 时，四次填入的位置依次是左上、右上、右下、左下，得到 [[1, 2], [4, 3]]。

当 cur 超过 n * n，说明所有数字都已填完。最后一次更新位置之后，循环不会再访问下一个格子。

3. 代码实现

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] walked = new int[n][n];
        int[][] directions = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int i = 0, j = 0;
        int t = 0;
        int[][] res = new int[n][n];
        int cur = 1;
        while (cur <= n * n) {
            res[i][j] = cur++;
            walked[i][j]++;
            int nexti = i + directions[t][0];
            int nextj = j + directions[t][1];
            if (nexti < 0 || nexti >= n || nextj < 0 || nextj >= n || walked[nexti][nextj] > 0) {
                t = (t + 1) % 4;
            }
            i += directions[t][0];
            j += directions[t][1];
        }
        return res;
    }
}

4. 复杂度分析

• 时间复杂度：O(n²)，填写矩阵中的全部 n² 个元素。
• 额外空间复杂度：O(n²)，实现中使用 walked 记录已填写的位置，不计返回矩阵。

5. 关联问题

矩阵的各种遍历方式：

1. 54. 螺旋矩阵
2. 59. 螺旋矩阵 II
3. 498. 对角线遍历

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明