LeetCode 59 - 螺旋矩阵 II（Spiral Matrix II）

算法刷题>LeetCode>面试经典150
12k words

LeetCode 59 - 螺旋矩阵 II

问题描述

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

示例

示例 1：

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

可视化表示：

1
2
3
→ → →
↑   ↓
↑ ← ↓

数字填充顺序：1→2→3→4→5→6→7→8→9

示例 2：

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

约束

  • 1 <= n <= 20

解题思路

方法一：模拟法（按方向遍历）

关键洞见：按照”右 → 下 → 左 → 上”的顺序依次填充矩阵，每次填充一个方向直到遇到边界或已填充位置，然后转向下一个方向。

算法流程：

  1. 初始化：创建一个 n × n 的矩阵，所有元素初始化为 0（或 -1 作为未填充标记）
  2. 定义方向：使用方向数组 dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]] 分别表示右、下、左、上四个方向
  3. 填充过程：
    • 从位置 (0, 0) 开始，初始方向为”右”（索引 0）
    • 对每个位置 (row, col)：
      • 如果当前格子未填充且未越界，填入当前数字 num，然后 num++
      • 计算下一个位置 (nextRow, nextCol)
      • 如果下一个位置越界或已填充，改变方向（dirIndex = (dirIndex + 1) % 4），重新计算下一个位置
    • 重复直到填充完 n² 个数字

边界控制要点：

  • 使用 0 或 -1 标记未填充位置
  • 判断下一个位置：nextRow = row + dirs[dirIndex][0]，nextCol = col + dirs[dirIndex][1]
  • 检查条件：nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || matrix[nextRow][nextCol] != 0
  • 满足任一条件时，转向下一个方向

手把手执行示例（n = 3）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
初始状态：
┌───┬───┬───┐
│ 0 │ 0 │ 0 │
├───┼───┼───┤
│ 0 │ 0 │ 0 │
├───┼───┼───┤
│ 0 │ 0 │ 0 │
└───┴───┴───┘

步骤1-3（向右）：(0,0)→1, (0,1)→2, (0,2)→3
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 0 │ 0 │ 0 │
├───┼───┼───┤
│ 0 │ 0 │ 0 │
└───┴───┴───┘
(0,3) 越界，转向"下"

步骤4-5（向下）：(1,2)→4, (2,2)→5
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 0 │ 0 │ 4 │
├───┼───┼───┤
│ 0 │ 0 │ 5 │
└───┴───┴───┘
(3,2) 越界，转向"左"

步骤6-7（向左）：(2,1)→6, (2,0)→7
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 0 │ 0 │ 4 │
├───┼───┼───┤
│ 7 │ 6 │ 5 │
└───┴───┴───┘
(2,-1) 越界，转向"上"

步骤8（向上）：(1,0)→8
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 8 │ 0 │ 4 │
├───┼───┼───┤
│ 7 │ 6 │ 5 │
└───┴───┴───┘
(0,0) 已填充，转向"右"

步骤9（向右）：(1,1)→9
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 8 │ 9 │ 4 │
├───┼───┼───┤
│ 7 │ 6 │ 5 │
└───┴───┴───┘
完成！

方法二：按层填充（Layer-by-Layer）- 左闭右开原则

关键洞见：将矩阵分为多个”层”（环），从外层到内层依次填充。对于 n × n 矩阵，共有 $\lceil n/2 \rceil$ 层。

思路形成路径

观察现象：螺旋填充是”一圈一圈”进行的，从最外层开始，逐渐向内层收缩。

提炼规律：圈数的数学分析

对于 n × n 矩阵：

  • 偶数情况（如 n = 4）：有 4/2 = 2 圈
    1
    2
    外层圈：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
    内层圈：12, 13, 14, 15
  • 奇数情况（如 n = 5）：有 5/2 = 2 圈（整数除法），加上中心点
    1
    2
    3
    外层圈：0, 1, 2, ..., 15
    内层圈：16, 17, 18, 19
    中心点：20

数学证明：

  • 第 i 圈（从 0 开始）的边长：n - 2i
  • 第 i 圈的元素数量：当 i < n/2 时，为 4(n - 2i - 1)（每条边有 n - 2i - 1 个元素，4条边）
  • 最大圈数：当 i = n/2 - 1 时，最后一圈开始，因此循环条件为 loop <= n/2（或 loop < n/2 在循环外处理中心）

实际上，使用 loop <= n/2 是因为：

  • 当 n 为偶数时，n/2 圈后正好填满
  • 当 n 为奇数时，n/2 圈后还剩中心一个点，需要单独处理

设计细节：左闭右开原则

遵循循环不变量原则，使用”左闭右开”设计每一圈的填充逻辑，这样可以：

  1. 避免重复填充：每条边的终点是下一条边的起点，左闭右开确保每条边只填充一次
  2. 边界清晰：循环条件统一为 j < n - offset（不包括终点）
  3. 代码简洁：不需要额外的边界检查

左闭右开原则在螺旋矩阵中的应用：

对于每一圈，定义：

  • startX, startY：当前圈的起始坐标
  • offset：当前圈的偏移量（第 loop 圈的 offset = loop）
  • 四条边的填充规则（左闭右开）：
    • 上边：j ∈ [startY, n - offset)，填充 [startX][j]
    • 右边：i ∈ [startX, n - offset)，填充 [i][n - offset]
    • 下边：j ∈ (startY, n - offset]，即从 n - offset 递减到 startY + 1，填充 [n - offset][j]
    • 左边：i ∈ (startX, n - offset]，即从 n - offset 递减到 startX + 1，填充 [i][startY]

处理例外：奇数矩阵的中心单独赋值

当 n % 2 == 1 时，循环结束后 startX == startY == n/2，正好是中心位置，单独赋值即可。

算法流程（左闭右开实现）

  1. 初始化：

    • 创建 n × n 矩阵
    • startX = 0, startY = 0：每一圈的起始点
    • offset = 1：偏移量（初始为 1，每圈后递增）
    • count = 1：要填入的数字
    • loop = 1：当前圈数

  2. 循环填充：while (loop <= n / 2)

    • 上边（从左到右）：j ∈ [startY, n - offset)，填充后 j 停在 n - offset
    • 右边（从上到下）：i ∈ [startX, n - offset)，填充后 i 停在 n - offset
    • 下边（从右到左）：j 从 n - offset - 1 递减到 startY + 1（即 j > startY），填充后 j 停在 startY
    • 左边（从下到上）：i 从 n - offset - 1 递减到 startX + 1（即 i > startX），填充后 i 停在 startX
    • 更新：startX++, startY++, offset++, loop++

  3. 处理中心：if (n % 2 == 1)，单独赋值中心点

手把手执行示例（n = 4）- 左闭右开原则

Loop 1：startX=0, startY=0, offset=1

上边（从左到右）：j ∈ [0, 4-1) = [0, 3)，填充 (0,0)=1, (0,1)=2, (0,2)=3

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ ? │  ← j停在3（不填充，因为j < n-offset不满足）
├───┼───┼───┼───┤
│ ? │ ? │ ? │ ? │
├───┼───┼───┼───┤
│ ? │ ? │ ? │ ? │
├───┼───┼───┼───┤
│ ? │ ? │ ? │ ? │
└───┴───┴───┴───┘

右边（从上到下）：i ∈ [0, 4-1) = [0, 3)，此时 j = 3（上边循环结束后的值），填充 (0,3)=4, (1,3)=5, (2,3)=6

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│ ? │ ? │ ? │ 5 │  ← i停在3（不填充）
├───┼───┼───┼───┤
│ ? │ ? │ ? │ 6 │
├───┼───┼───┼───┤
│ ? │ ? │ ? │ ? │
└───┴───┴───┴───┘

下边（从右到左）：此时 i = 3, j = 3，j > startY 即 j > 0，填充 (3,2)=7, (3,1)=8, (3,0)=9

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│ ? │ ? │ ? │ 5 │
├───┼───┼───┼───┤
│ ? │ ? │ ? │ 6 │
├───┼───┼───┼───┤
│ 9 │ 8 │ 7 │ ? │  ← j停在0（不填充，因为j > startY不满足）
└───┴───┴───┴───┘

左边（从下到上）：此时 i = 3, j = 0，i > startX 即 i > 0，填充 (2,0)=10, (1,0)=11

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│11 │ ? │ ? │ 5 │  ← i停在0（不填充）
├───┼───┼───┼───┤
│10 │ ? │ ? │ 6 │
├───┼───┼───┼───┤
│ 9 │ 8 │ 7 │ ? │
└───┴───┴───┴───┘

更新：startX=1, startY=1, offset=2, loop=2

Loop 2：startX=1, startY=1, offset=2

上边：j ∈ [1, 4-2) = [1, 2)，填充 (1,1)=12

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│11 │12 │ ? │ 5 │  ← j停在2
├───┼───┼───┼───┤
│10 │ ? │ ? │ 6 │
├───┼───┼───┼───┤
│ 9 │ 8 │ 7 │ ? │
└───┴───┴───┴───┘

右边：i ∈ [1, 4-2) = [1, 2)，填充 (1,2)=13

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│11 │12 │13 │ 5 │  ← i停在2
├───┼───┼───┼───┤
│10 │ ? │ ? │ 6 │
├───┼───┼───┼───┤
│ 9 │ 8 │ 7 │ ? │
└───┴───┴───┴───┘

下边：j 从 1 递减，但 j > startY 即 j > 1 不满足，所以不填充（因为下边已经在上一次循环结束时被填充过了）

左边：i 从 1 递减，但 i > startX 即 i > 1 不满足，所以不填充

循环结束，n=4 为偶数，无需处理中心。

最终结果：

1
2
3
4
5
6
7
8
9
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│12 │13 │14 │ 5 │
├───┼───┼───┼───┤
│11 │16 │15 │ 6 │
├───┼───┼───┼───┤
│10 │ 9 │ 8 │ 7 │
└───┴───┴───┴───┘

关键观察：

  • 左闭右开的优势：每条边的终点恰好是下一条边的起点（如上边的 j=3 是右边的起始列），避免了重复填充
  • 边界统一：所有边界判断都使用 j < n-offset 或 j > startY 的形式，逻辑清晰

代码实现

Java - 模拟法（按方向遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右、下、左、上
        int row = 0, col = 0;
        int dirIndex = 0; // 初始方向为"右"
        int num = 1;
        
        while (num <= n * n) {
            matrix[row][col] = num++;
            
            // 计算下一个位置
            int nextRow = row + dirs[dirIndex][0];
            int nextCol = col + dirs[dirIndex][1];
            
            // 如果下一个位置越界或已填充，改变方向
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n 
                || matrix[nextRow][nextCol] != 0) {
                dirIndex = (dirIndex + 1) % 4;
                nextRow = row + dirs[dirIndex][0];
                nextCol = col + dirs[dirIndex][1];
            }
            
            row = nextRow;
            col = nextCol;
        }
        
        return matrix;
    }
}

Java - 按层填充法（左闭右开原则，推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0; // 每一圈的起始点
        int offset = 1; // 偏移量
        int count = 1; // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // 行列

        while (loop <= n / 2) {
            // 顶部：左闭右开，所以判断结束时，j不能等于n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列：左闭右开，所以判断循环结束时，i不能等于n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部：左闭右开，所以判断结束时，j不等于startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列：左闭右开，所以判断结束时，i不等于startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }

            startX++;
            startY++;
            offset++;
            loop++;
        }
        
        if (n % 2 == 1) {
            // n为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        
        return nums;
    }
}

变量详解与设计思路：

变量含义与作用

变量名 类型 初始值 作用 为什么需要这个变量
startX int 0 当前圈的起始行坐标 标记每圈填充的起始行，用于控制”左边”和”上边”的起始位置
startY int 0 当前圈的起始列坐标 标记每圈填充的起始列，用于控制”上边”和”下边”的起始位置
offset int 1 当前圈的边界偏移量 用于计算每圈的右边界和下边界：n - offset，实现”内缩”效果
count int 1 当前要填入矩阵的数字 记录填充进度，从 1 递增到 $n^2$，每填充一个格子后自增
loop int 1 当前正在填充的圈数 控制循环次数，从第 1 圈到第 $\lfloor n/2 \rfloor$ 圈
i int 未初始化 当前填充位置的行索引 在四个方向的循环中复用，自动传递位置信息
j int 未初始化 当前填充位置的列索引 在四个方向的循环中复用，自动传递位置信息

变量设计思路

为什么选择这 7 个变量？

  1. 定位变量组（startX, startY, offset）：描述当前圈的边界信息

    设计思考：

    • 问题：每圈填充时，边界都在”内缩”，如何统一描述？
    • 方案 A：使用 left, right, top, bottom（4 个变量）❌
      • 优点：直观，边界清晰
      • 缺点：变量多，每次更新需要同时修改多个变量
    • 方案 B：使用 startX, startY, offset（3 个变量）✅ 采用
      • 优点：
        • 对称性：startX 和 startY 对称，代码更简洁
        • 统一性：offset 统一控制”缩进”，左右、上下边界都通过 n - offset 计算
        • 内聚性：三个变量共同描述一个”圈”的状态
      • 数学关系：
        1
        2
        3
        4
        5
        第 loop 圈：
        - 上边界：startX (初始为 0，每圈 +1)
        - 左边界：startY (初始为 0，每圈 +1)
        - 右边界：n - offset (初始为 n-1，每圈 -1，即 offset++)
        - 下边界：n - offset (初始为 n-1，每圈 -1，即 offset++)
      • 为什么 offset 从 1 开始？
        • 第 1 圈：offset = 1，右边界 = n - 1（最后一个有效列）
        • 第 2 圈：offset = 2，右边界 = n - 2（倒数第二个有效列）
        • 这样设计使边界计算统一：n - offset

  2. 进度变量（count, loop）：跟踪填充进度

    设计思考：

    • count：记录”填什么”
      • 从 1 到 $n^2$，每次 count++
      • 选择原因：直观，符合题目要求（填充 1 到 $n^2$）
    • loop：记录”填第几圈”
      • 从 1 到 n/2，用于循环控制
      • 选择原因：与循环条件 loop <= n/2 直接对应，语义清晰

  3. 位置变量（i, j）：当前填充位置，实现变量复用

    设计思考：

    • 问题：四个方向的循环如何衔接？
    • 方案 A：每个循环独立定义变量 ❌
      1
      2
      for (int j = startY; j < n - offset; j++) { ... }
      for (int i = startX; i < n - offset; i++) { ... }
      • 缺点：需要额外计算下一个循环的起始值
    • 方案 B：外部定义 i, j，循环间自动传递 ✅ 采用
      1
      2
      3
      int i, j;
      for (j = startY; j < n - offset; j++) { ... }  // j 停在 n-offset
      for (i = startX; i < n - offset; i++) { ... }   // 使用 j，i 停在 n-offset
      • 核心优势：利用循环结束后的变量值，实现自动衔接
      • 左闭右开的妙处：
        1
        2
        上边循环：j ∈ [startY, n-offset)，结束时 j = n-offset
        右边循环：i ∈ [startX, n-offset)，结束时 i = n-offset
        • 上边的”终点” (startX, n-offset) 恰好是右边的”起点”
        • 右边的”终点” (n-offset, n-offset) 恰好是下边的”起点”
        • 变量自动传递，无需手动计算

变量初始化与更新规律

初始化：

1
2
3
4
5
6
int startX = 0;      // 从矩阵左上角开始
int startY = 0;      // 从矩阵左上角开始
int offset = 1;      // 第一圈的右边界是 n-1
int count = 1;       // 从数字 1 开始填充
int loop = 1;        // 从第 1 圈开始
int i, j;            // 未初始化，在第一个循环中首次赋值

每圈结束后的更新规律：

1
2
3
4
5
6
startX++;    // 下一圈的起始行 = 当前起始行 + 1（向内缩进）
startY++;    // 下一圈的起始列 = 当前起始列 + 1（向内缩进）
offset++;    // 下一圈的边界偏移量 + 1（右边界和下边界都左移/上移 1）
loop++;      // 圈数 + 1
// count 在每个填充操作中自动递增，无需手动更新
// i, j 在下一圈的循环中重新赋值

变量关系可视化（n = 4）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
初始状态（Loop 1 开始）：
startX = 0, startY = 0, offset = 1

矩阵边界示意：
┌─────────────────────────┐
│ (0,0)  ← startX,startY  │ ← 上边界 = startX = 0
│         ┌───────┐       │
│         │       │       │
│         │  内圈 │       │
│         │       │       │
│         └───────┘       │
│                  (3,3)  │
└─────────────────────────┘
左边界=startY=0         右边界=n-offset=3  下边界=n-offset=3

Loop 1 填充过程（i, j 的变化轨迹）：
1. 上边：j 从 0 到 2（j < 3），填充 (0,0),(0,1),(0,2)
   → j 停在 3（n-offset）
2. 右边：i 从 0 到 2（i < 3），j 复用为 3，填充 (0,3),(1,3),(2,3)
   → i 停在 3（n-offset）
3. 下边：j 从 2 到 1（j > 0），i 复用为 3，填充 (3,2),(3,1)
   → j 停在 0（startY）
4. 左边：i 从 2 到 1（i > 0），j 复用为 0，填充 (2,0),(1,0)
   → i 停在 0（startX）

Loop 1 结束后更新：
startX = 1, startY = 1, offset = 2

┌─────────────────────────┐
│ (0,0) (0,1) (0,2) (0,3) │
│ (1,0) ┌───────┐ (1,3)  │
│ (2,0)│  内圈 │ (2,3)  │ ← 新的 startX=1, startY=1
│ (3,0)│       │ (3,3)  │
│      └───────┘        │
│ (3,0) (3,1) (3,2)      │
└─────────────────────────┘

Loop 2 填充过程：
新的边界：左边界=1，上边界=1，右边界=n-offset=2，下边界=n-offset=2
1. 上边：j 从 1 到 1（j < 2），填充 (1,1)
2. 右边：i 从 1 到 1（i < 2），填充 (1,2)
3. 下边：j > 1 不满足，不填充
4. 左边：i > 1 不满足，不填充

最终：loop = 3 > 4/2 = 2，循环结束

示例追踪（n = 4）：

圈数 startX startY offset 右边界 (n-offset) 下边界 (n-offset) count 范围 说明
初始 0 0 1 3 3 1 外圈：从 (0,0) 到 (3,3)
Loop 1 0 0 1 3 3 1→12 填充外圈：12个元素
更新后 1 1 2 2 2 13 内圈：从 (1,1) 到 (2,2)
Loop 2 1 1 2 2 2 13→16 填充内圈：4个元素
结束 2 2 3 1 1 - loop = 3 > 4/2 = 2，循环结束

变量依赖关系图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
loop (圈数)
  ↓
  ├─→ startX = loop - 1 (第 loop 圈的起始行)
  ├─→ startY = loop - 1 (第 loop 圈的起始列)
  └─→ offset = loop (第 loop 圈的偏移量)
       ↓
       ├─→ 右边界 = n - offset
       └─→ 下边界 = n - offset

i, j (位置变量)
  ↓
  在四个循环间自动传递：
  上边循环 → j = n-offset → 右边循环
  右边循环 → i = n-offset → 下边循环
  下边循环 → j = startY → 左边循环
  左边循环 → i = startX → 回到起点

为什么这样设计？

核心设计原则：

  1. 最小变量原则：用最少的变量表达完整的状态

    • 3 个定位变量（startX, startY, offset）替代 4 个边界变量
    • 利用对称性和统一性减少变量数量

  2. 变量复用原则：i, j 在循环间自动传递

    • 减少重复计算
    • 体现”左闭右开”的优势

  3. 语义清晰原则：变量名直接反映用途

    • startX/Y：起始点
    • offset：偏移量
    • loop：圈数
    • count：计数

  4. 内聚性原则：相关变量一起更新

    • startX++, startY++, offset++ 同时更新，保持一致性

代码要点解析：

  1. 循环条件 loop <= n / 2：

    • n = 4（偶数）：4/2 = 2，循环2次，刚好填满
    • n = 5（奇数）：5/2 = 2（整数除法），循环2次，中心点单独处理

  2. 左闭右开原则的应用：

    • 上边：j ∈ [startY, n-offset)，不包括 n-offset，避免与右边重复
    • 右边：i ∈ [startX, n-offset)，利用上边循环结束后的 j 值（此时 j = n-offset）
    • 下边：j > startY，从 n-offset-1 递减到 startY+1，不包括 startY（避免与上边重复）
    • 左边：i > startX，从 n-offset-1 递减到 startX+1，不包括 startX（避免与右边重复）

  3. 变量复用：

    • 上边循环结束后，j 的值正好是 n-offset，作为右边的起始列
    • 右边循环结束后，i 的值正好是 n-offset，作为下边的起始行
    • 下边循环结束后，j 的值正好是 startY，作为左边的起始列
    • 左边循环结束后，i 的值正好是 startX，回到起始行

  4. 奇数中心处理：

    • 当 n 为奇数时，循环结束后 startX = startY = n/2，正好是中心位置
    • 单独赋值最后一个数字即可

Java - 按层填充法（边界变量法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int num = 1;
        int left = 0, right = n - 1;
        int top = 0, bottom = n - 1;
        
        while (left <= right && top <= bottom) {
            // 填充上边：从左到右
            for (int col = left; col <= right; col++) {
                matrix[top][col] = num++;
            }
            top++;
            
            // 填充右边：从上到下
            for (int row = top; row <= bottom; row++) {
                matrix[row][right] = num++;
            }
            right--;
            
            // 填充下边：从右到左（需要检查是否还有行）
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    matrix[bottom][col] = num++;
                }
                bottom--;
            }
            
            // 填充左边：从下到上（需要检查是否还有列）
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    matrix[row][left] = num++;
                }
                left++;
            }
        }
        
        return matrix;
    }
}

方法比较

方面 模拟法（方向遍历） 按层填充法（边界变量） 按层填充法（左闭右开）
时间复杂度 $O(n^2)$ $O(n^2)$ $O(n^2)$
空间复杂度 $O(1)$（不含输出） $O(1)$（不含输出） $O(1)$（不含输出）
代码复杂度 中 低 低
边界控制 需要检查下一个位置 边界清晰，需要条件判断 边界统一，左闭右开避免重复
循环不变量 无明确原则 无明确原则 遵循左闭右开原则
变量复用 否 否 是（i, j 自动传递）
推荐度 ★★★☆☆ ★★★★☆ ★★★★★

推荐使用左闭右开原则的按层填充法：

  • 边界条件统一，遵循循环不变量原则，逻辑清晰
  • 变量自动复用（i, j 在各循环间传递），代码简洁
  • 左闭右开设计避免了重复填充，无需额外的边界检查
  • 易于理解和维护，是工程实践中的最佳选择

复杂度分析

  • 时间复杂度：$O(n^2)$。需要填充 $n^2$ 个元素，每个元素填充一次。
  • 空间复杂度：$O(1)$（不含输出矩阵）。两种方法都只使用了常数额外空间（方向数组、边界变量等）。

常见陷阱与注意事项

陷阱 1：边界检查不完整

错误代码：

1
2
3
4
// 错误：只检查了数组边界，没有检查已填充位置
if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n) {
    dirIndex = (dirIndex + 1) % 4;
}

正确做法：同时检查边界和已填充状态。

陷阱 2：按层填充时忘记检查剩余行列

错误代码：

1
2
3
4
5
6
7
8
9
// 错误：在填充下边和左边时没有检查 top <= bottom 和 left <= right
for (int col = right; col >= left; col--) {
    matrix[bottom][col] = num++;
}
bottom--;

for (int row = bottom; row >= top; row--) {
    matrix[row][left] = num++;
}

原因：当 n 为奇数时，最后可能只剩中心一个元素，此时 top > bottom 或 left > right，如果不检查会重复填充。

陷阱 3：方向数组索引错误

确保方向数组的顺序与填充顺序一致：右 → 下 → 左 → 上。

关键收获

  • 模拟类问题：螺旋矩阵问题本质上是模拟填充过程，关键在于边界控制和方向转换。
  • 按层思维：将矩阵视为多个同心环，逐层填充可以简化逻辑。
  • 圈数计算 loop <= n/2：
    • 数学原理：n × n 矩阵有 $\lceil n/2 \rceil$ 层（圈）
    • 偶数情况：n/2 圈后正好填满，无需特殊处理
    • 奇数情况：n/2 圈（整数除法）后还剩中心一个点，需要单独赋值
    • 循环设计：使用 loop <= n/2 可以统一处理奇偶两种情况
  • 左闭右开原则（循环不变量）：
    • 设计思想：遵循循环不变量原则，统一边界处理逻辑
    • 核心优势：每条边的终点是下一条边的起点，自然避免重复填充
    • 实现要点：
      • 上边：j < n-offset（不包括右边界）
      • 右边：i < n-offset（不包括下边界）
      • 下边：j > startY（不包括左边界）
      • 左边：i > startX（不包括上边界）
    • 变量复用：利用循环结束后变量的值，自动传递到下一个循环
  • 边界检查：必须同时检查数组边界和已填充状态，避免重复填充或越界。
  • 奇数矩阵处理：当 n 为奇数时，中心元素需要特殊处理，循环结束后 startX = startY = n/2 正好是中心位置。
  • 工程实践：左闭右开原则不仅适用于螺旋矩阵，也是算法设计中的重要思想，能显著简化边界处理逻辑。

相关问题

  • LeetCode 54 - 螺旋矩阵：与本题相反，给定矩阵按螺旋顺序读取元素。
  • LeetCode 885 - 螺旋矩阵 III：在给定起始位置和方向的情况下生成螺旋矩阵。