59. 螺旋矩阵 II

约 3853 字大约 13 分钟

数组矩阵模拟

2025-06-07

🔗 LeetCode原题链接

📝 原题

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 20

🤔 审题

💡 面试小提示：在算法面试中，审题环节极其重要！不要急于写代码，先确保你完全理解了题目要求。

假设你正在面试中，面对这道题目，你可以向面试官提出以下问题来澄清需求：

输入规模："题目说n的范围是1到20，这意味着最大的矩阵是20×20，最多需要填充400个数字，对吗？"
边界情况："对于n=1的情况，我只需要返回[[1]]这样的矩阵，是吗？"
返回要求："我需要返回的是一个二维数组，其中包含按照螺旋顺序排列的1到n²的所有数字，对吗？"

通过这些问题，我们可以更清晰地了解题目要求，避免做无用功或者遗漏重要条件。

💡 解题思路

方法一：模拟法

思路概述

这道题的核心思路其实很直观：我们需要模拟顺时针螺旋填充数字的过程。想象一下，我们从矩阵的左上角开始，先向右走，走到头后向下走，走到头后向左走，走到头后向上走，形成一个螺旋。每走一步，我们就在当前位置填入下一个数字。

这个过程可以通过维护四个边界变量来实现：top、right、bottom和left，它们分别表示当前螺旋的上、右、下、左边界。每完成一个方向的填充，相应的边界就会向内收缩一格。

图解演示

以n=3为例，我们来看看螺旋填充的过程：

初始状态：创建一个3×3的空矩阵，边界为top=0, right=2, bottom=2, left=0
第一轮填充：
- 从左到右填充第一行：[1,2,3]
- 从上到下填充最右列：[,,4]
- 从右到左填充最下行：[_,6,5]
- 从下到上填充最左列：[,7,]
第二轮填充：
- 从左到右填充中间行的中间位置：[,8,]
- 此时所有边界都已收缩，只剩中心点：[,9,]

最终得到矩阵：[[1,2,3],[8,9,4],[7,6,5]]

算法步骤

创建一个n×n的矩阵，初始值都为0
定义四个边界变量：top=0, right=n-1, bottom=n-1, left=0
定义当前要填入的数字num=1
当num <= n²时，执行以下步骤：
- 从left到right填充第top行
- top加1（上边界下移）
- 从top到bottom填充第right列
- right减1（右边界左移）
- 如果top <= bottom，从right到left填充第bottom行
- bottom减1（下边界上移）
- 如果left <= right，从bottom到top填充第left列
- left加1（左边界右移）
返回填充完成的矩阵

复杂度分析

时间复杂度：O(n²)，因为我们需要填充n²个格子，每个格子只填充一次
空间复杂度：O(n²)，需要创建一个n×n的矩阵来存储结果

💻 源码实现

核心代码模式

💡 提示：核心代码模式只包含算法的主体部分，可以直接复制到LeetCode中提交。

Java

class Solution {
    public int[][] generateMatrix(int n) {
        // 创建结果矩阵
        int[][] result = new int[n][n];
        
        // 定义四个边界
        int top = 0, right = n - 1, bottom = n - 1, left = 0;
        
        // 当前要填入的数字
        int num = 1;
        
        // 循环填充矩阵
        while (num <= n * n) {
            // 从左到右填充上边界
            for (int i = left; i <= right; i++) {
                result[top][i] = num++;
            }
            top++; // 上边界下移
            
            // 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                result[i][right] = num++;
            }
            right--; // 右边界左移
            
            // 从右到左填充下边界
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result[bottom][i] = num++;
                }
                bottom--; // 下边界上移
            }
            
            // 从下到上填充左边界
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result[i][left] = num++;
                }
                left++; // 左边界右移
            }
        }
        
        return result;
    }
}

Python

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 创建结果矩阵
        result = [[0] * n for _ in range(n)]
        
        # 定义四个边界
        top, right, bottom, left = 0, n - 1, n - 1, 0
        
        # 当前要填入的数字
        num = 1
        
        # 循环填充矩阵
        while num <= n * n:
            # 从左到右填充上边界
            for i in range(left, right + 1):
                result[top][i] = num
                num += 1
            top += 1  # 上边界下移
            
            # 从上到下填充右边界
            for i in range(top, bottom + 1):
                result[i][right] = num
                num += 1
            right -= 1  # 右边界左移
            
            # 从右到左填充下边界
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    result[bottom][i] = num
                    num += 1
                bottom -= 1  # 下边界上移
            
            # 从下到上填充左边界
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result[i][left] = num
                    num += 1
                left += 1  # 左边界右移
                
        return result

JavaScript

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    // 创建结果矩阵
    const result = Array(n).fill(0).map(() => Array(n).fill(0));
    
    // 定义四个边界
    let top = 0, right = n - 1, bottom = n - 1, left = 0;
    
    // 当前要填入的数字
    let num = 1;
    
    // 循环填充矩阵
    while (num <= n * n) {
        // 从左到右填充上边界
        for (let i = left; i <= right; i++) {
            result[top][i] = num++;
        }
        top++; // 上边界下移
        
        // 从上到下填充右边界
        for (let i = top; i <= bottom; i++) {
            result[i][right] = num++;
        }
        right--; // 右边界左移
        
        // 从右到左填充下边界
        if (top <= bottom) {
            for (let i = right; i >= left; i--) {
                result[bottom][i] = num++;
            }
            bottom--; // 下边界上移
        }
        
        // 从下到上填充左边界
        if (left <= right) {
            for (let i = bottom; i >= top; i--) {
                result[i][left] = num++;
            }
            left++; // 左边界右移
        }
    }
    
    return result;
};

func generateMatrix(n int) [][]int {
    // 创建结果矩阵
    result := make([][]int, n)
    for i := range result {
        result[i] = make([]int, n)
    }
    
    // 定义四个边界
    top, right, bottom, left := 0, n-1, n-1, 0
    
    // 当前要填入的数字
    num := 1
    
    // 循环填充矩阵
    for num <= n*n {
        // 从左到右填充上边界
        for i := left; i <= right; i++ {
            result[top][i] = num
            num++
        }
        top++ // 上边界下移
        
        // 从上到下填充右边界
        for i := top; i <= bottom; i++ {
            result[i][right] = num
            num++
        }
        right-- // 右边界左移
        
        // 从右到左填充下边界
        if top <= bottom {
            for i := right; i >= left; i-- {
                result[bottom][i] = num
                num++
            }
            bottom-- // 下边界上移
        }
        
        // 从下到上填充左边界
        if left <= right {
            for i := bottom; i >= top; i-- {
                result[i][left] = num
                num++
            }
            left++ // 左边界右移
        }
    }
    
    return result
}

ACM模式

💡 提示：ACM模式包含完整的输入输出处理，可以在本地IDE中运行并测试。

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        
        int[][] result = generateMatrix(n);
        
        // 输出结果
        System.out.print("[");
        for (int i = 0; i < n; i++) {
            System.out.print("[");
            for (int j = 0; j < n; j++) {
                System.out.print(result[i][j]);
                if (j < n - 1) {
                    System.out.print(",");
                }
            }
            System.out.print("]");
            if (i < n - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }
    
    public static int[][] generateMatrix(int n) {
        // 创建结果矩阵
        int[][] result = new int[n][n];
        
        // 定义四个边界
        int top = 0, right = n - 1, bottom = n - 1, left = 0;
        
        // 当前要填入的数字
        int num = 1;
        
        // 循环填充矩阵
        while (num <= n * n) {
            // 从左到右填充上边界
            for (int i = left; i <= right; i++) {
                result[top][i] = num++;
            }
            top++; // 上边界下移
            
            // 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                result[i][right] = num++;
            }
            right--; // 右边界左移
            
            // 从右到左填充下边界
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result[bottom][i] = num++;
                }
                bottom--; // 下边界上移
            }
            
            // 从下到上填充左边界
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result[i][left] = num++;
                }
                left++; // 左边界右移
            }
        }
        
        return result;
    }
}

Python

def generate_matrix(n):
    # 创建结果矩阵
    result = [[0] * n for _ in range(n)]
    
    # 定义四个边界
    top, right, bottom, left = 0, n - 1, n - 1, 0
    
    # 当前要填入的数字
    num = 1
    
    # 循环填充矩阵
    while num <= n * n:
        # 从左到右填充上边界
        for i in range(left, right + 1):
            result[top][i] = num
            num += 1
        top += 1  # 上边界下移
        
        # 从上到下填充右边界
        for i in range(top, bottom + 1):
            result[i][right] = num
            num += 1
        right -= 1  # 右边界左移
        
        # 从右到左填充下边界
        if top <= bottom:
            for i in range(right, left - 1, -1):
                result[bottom][i] = num
                num += 1
            bottom -= 1  # 下边界上移
        
        # 从下到上填充左边界
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result[i][left] = num
                num += 1
            left += 1  # 左边界右移
            
    return result

if __name__ == "__main__":
    n = int(input().strip())
    result = generate_matrix(n)
    
    # 输出结果
    print("[", end="")
    for i in range(n):
        print("[", end="")
        for j in range(n):
            print(result[i][j], end="")
            if j < n - 1:
                print(",", end="")
        print("]", end="")
        if i < n - 1:
            print(",", end="")
    print("]")

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (n) => {
    n = parseInt(n);
    const result = generateMatrix(n);
    
    // 输出结果
    let output = "[";
    for (let i = 0; i < n; i++) {
        output += "[";
        for (let j = 0; j < n; j++) {
            output += result[i][j];
            if (j < n - 1) {
                output += ",";
            }
        }
        output += "]";
        if (i < n - 1) {
            output += ",";
        }
    }
    output += "]";
    
    console.log(output);
    rl.close();
});

function generateMatrix(n) {
    // 创建结果矩阵
    const result = Array(n).fill(0).map(() => Array(n).fill(0));
    
    // 定义四个边界
    let top = 0, right = n - 1, bottom = n - 1, left = 0;
    
    // 当前要填入的数字
    let num = 1;
    
    // 循环填充矩阵
    while (num <= n * n) {
        // 从左到右填充上边界
        for (let i = left; i <= right; i++) {
            result[top][i] = num++;
        }
        top++; // 上边界下移
        
        // 从上到下填充右边界
        for (let i = top; i <= bottom; i++) {
            result[i][right] = num++;
        }
        right--; // 右边界左移
        
        // 从右到左填充下边界
        if (top <= bottom) {
            for (let i = right; i >= left; i--) {
                result[bottom][i] = num++;
            }
            bottom--; // 下边界上移
        }
        
        // 从下到上填充左边界
        if (left <= right) {
            for (let i = bottom; i >= top; i--) {
                result[i][left] = num++;
            }
            left++; // 左边界右移
        }
    }
    
    return result;
}

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    
    result := generateMatrix(n)
    
    // 输出结果
    fmt.Print("[")
    for i := 0; i < n; i++ {
        fmt.Print("[")
        for j := 0; j < n; j++ {
            fmt.Print(result[i][j])
            if j < n-1 {
                fmt.Print(",")
            }
        }
        fmt.Print("]")
        if i < n-1 {
            fmt.Print(",")
        }
    }
    fmt.Println("]")
}

func generateMatrix(n int) [][]int {
    // 创建结果矩阵
    result := make([][]int, n)
    for i := range result {
        result[i] = make([]int, n)
    }
    
    // 定义四个边界
    top, right, bottom, left := 0, n-1, n-1, 0
    
    // 当前要填入的数字
    num := 1
    
    // 循环填充矩阵
    for num <= n*n {
        // 从左到右填充上边界
        for i := left; i <= right; i++ {
            result[top][i] = num
            num++
        }
        top++ // 上边界下移
        
        // 从上到下填充右边界
        for i := top; i <= bottom; i++ {
            result[i][right] = num
            num++
        }
        right-- // 右边界左移
        
        // 从右到左填充下边界
        if top <= bottom {
            for i := right; i >= left; i-- {
                result[bottom][i] = num
                num++
            }
            bottom-- // 下边界上移
        }
        
        // 从下到上填充左边界
        if left <= right {
            for i := bottom; i >= top; i-- {
                result[i][left] = num
                num++
            }
            left++ // 左边界右移
        }
    }
    
    return result
}

🔍 面试官追问

💡 面试提醒：在算法面试中，写出正确的代码只是第一步。面试官通常会追问一些问题，测试你对算法的理解深度和应变能力。

Q1: 这个算法的时间和空间复杂度是多少？你是如何分析的？

思路点拨：时间复杂度分析需要考虑我们访问了多少个元素。在这个问题中，我们需要填充n×n个格子，每个格子只访问一次，所以时间复杂度是O(n²)。

空间复杂度分析需要考虑我们使用了多少额外空间。除了返回的结果矩阵外，我们只使用了几个变量（top, right, bottom, left, num）来控制填充过程，这些变量占用的空间是常数级的。因此，如果不计算输出矩阵，额外空间复杂度是O(1)；如果计算输出矩阵，空间复杂度是O(n²)。

在面试中，通常会将输出结构计入空间复杂度，所以这道题的空间复杂度是O(n²)。

Q2: 如果要求逆时针螺旋填充矩阵，应该如何修改代码？

思路点拨：要改为逆时针螺旋填充，我们需要改变填充的顺序。原来的顺序是：右→下→左→上，逆时针的顺序应该是：下→右→上→左。

具体修改如下：

从上到下填充左边界
从左到右填充下边界
从下到上填充右边界
从右到左填充上边界

代码修改示例（Java）：

while (num <= n * n) {
    // 从上到下填充左边界
    for (int i = top; i <= bottom; i++) {
        result[i][left] = num++;
    }
    left++; // 左边界右移
    
    // 从左到右填充下边界
    for (int i = left; i <= right; i++) {
        result[bottom][i] = num++;
    }
    bottom--; // 下边界上移
    
    // 从下到上填充右边界
    if (left <= right) {
        for (int i = bottom; i >= top; i--) {
            result[i][right] = num++;
        }
        right--; // 右边界左移
    }
    
    // 从右到左填充上边界
    if (top <= bottom) {
        for (int i = right; i >= left; i--) {
            result[top][i] = num++;
        }
        top++; // 上边界下移
    }
}

Q3: 这道题有没有其他解法？或者有什么可以优化的地方？

思路点拨：这道题的模拟法已经是最直观且高效的解法了，时间复杂度O(n²)是最优的，因为我们必须填充所有n²个格子。

不过，我们可以考虑一些小的优化：

方向数组：可以使用方向数组来简化代码，使其更加简洁。例如，定义方向变量directions = [[0,1], [1,0], [0,-1], [-1,0]]（分别表示右、下、左、上），然后使用一个循环来处理四个方向的填充。
数学公式：对于特定位置(i,j)的元素，理论上可以通过数学公式直接计算出它应该填入的数字，但这种方法比较复杂，不如模拟法直观。
层次填充：可以将矩阵看作由多个"层"组成的，从外到内一层一层地填充。这种思路与我们当前的解法本质上是相同的，只是表达方式不同。

总的来说，对于这道题，模拟法已经是最佳选择，其他方法可能会使代码更复杂而没有明显的性能提升。

📚 相关题目推荐

如果你对这道题感兴趣，可以尝试解决以下相关题目：

54. 螺旋矩阵 - 与本题相反，给定一个矩阵，按螺旋顺序返回其中的所有元素
885. 螺旋矩阵 III - 在无限大的二维网格中，按螺旋顺序访问指定数量的格子

🌟 总结

螺旋矩阵II是一道经典的模拟题，它考察了我们对二维数组操作和边界处理的能力。解决这类问题的关键在于：

清晰的边界控制：通过维护四个边界变量（top, right, bottom, left），我们可以精确控制填充的范围
方向转换的处理：在到达边界时，需要及时转换填充方向并更新相应的边界
条件判断的重要性：在向左和向上填充时，需要先判断是否还有元素需要填充，避免重复填充

这种"层层向内"的填充思路不仅适用于螺旋矩阵问题，也可以应用到其他需要按特定顺序遍历二维数组的问题中。掌握了这种模拟技巧，你就能轻松应对各种矩阵遍历的变形题目。

记住，面试中遇到这类问题时，先理清思路，确定好边界条件和转向逻辑，再动手编码，这样能大大减少出错的可能性。

祝你面试顺利！💪

数组

哈希表

链表

动态规划