螺旋矩阵

约 3610 字大约 12 分钟

2025-05-14

引言

在算法学习和面试准备中，矩阵相关的题目层出不穷，它们能够有效地考察我们对数据结构的理解、逻辑思维能力以及处理边界条件的细致程度。“螺旋矩阵 II” (Spiral Matrix II) 就是这样一道经典的题目。它要求我们根据给定的正整数 n，生成一个 n x n 的正方形矩阵，其中包含从 1 到 n² 的所有元素，并且这些元素需要按照顺时针螺旋的顺序排列。这类问题不仅是面试中的常客，其解题思路也为我们理解更复杂的矩阵操作、图像处理中的扫描算法或游戏开发中的路径生成等问题提供了有益的启示。本文旨在为准备算法面试的工程师和高校学生提供一个清晰、详尽的解题指南，帮助大家深入理解该问题的核心思想与实现方法。

题目标签

数据结构：数组
算法类型：模拟
难度等级：中等
来源平台：LeetCode

审题

题目要求我们根据一个给定的正整数 n，创建一个 n x n 大小的二维数组（即正方形矩阵）。这个矩阵需要包含从 1 到 n² 的所有整数，并且这些整数必须按照顺时针螺旋的顺序填充到矩阵中。具体来说，数字 1 应该位于矩阵的左上角，然后数字 2 在其右侧，以此类推，沿着矩阵的外层顺时针填充，然后向内层继续顺时针填充，直到所有 n² 个数字都被填入。输入是一个正整数 n。输出则是一个 n x n 的二维整数数组，代表生成的螺旋矩阵。我们需要特别注意题目给出的提示，即 n 的取值范围是 1 <= n <= 20。这意味着当 n=1 时，我们应该输出一个只包含 [[1]] 的矩阵，这是一个需要考虑的边界情况。同时，由于 n 最大为 20，n² 最大为 400，生成的矩阵规模不会非常大，这对于我们思考算法的时间和空间复杂度有一定的指导意义。

初始化矩阵和边界：首先，创建一个 n x n 的二维数组 matrix，并用 0 (或其他标记未填充的值) 初始化所有元素。接着，定义四个变量来表示当前螺旋填充的边界：top 初始化为 0 (最上边的行索引)，bottom 初始化为 n - 1 (最下边的行索引)，left 初始化为 0 (最左边的列索引)，right 初始化为 n - 1 (最右边的列索引)。同时，初始化一个计数器 num = 1，用于记录当前要填充的数字。
循环填充：进入一个循环，循环条件是 left <= right 且 top <= bottom。这个条件确保了只要还有未填充的区域，循环就会继续。
从左到右填充上边界：在当前定义的上边界 top 行，从 left 列遍历到 right 列，将 matrix[top][i] 依次赋值为 num，并且每次赋值后 num 自增 1。完成这一行填充后，上边界向下收缩，即 top 增加 1。
从上到下填充右边界：接下来，在当前定义的右边界 right 列，从新的 top 行遍历到 bottom 行，将 matrix[i][right] 依次赋值为 num，并且 num 自增 1。完成这一列填充后，右边界向左收缩，即 right 减少 1。
从右到左填充下边界 (条件判断)：在进行下一步之前，需要判断是否还有必要继续填充。如果此时 top <= bottom（确保至少还有一行未被完全覆盖），则在当前定义的下边界 bottom 行，从新的 right 列反向遍历到 left 列，将 matrix[bottom][i] 依次赋值为 num，并且 num 自增 1。完成这一行填充后，下边界向上收缩，即 bottom 减少 1。
从下到上填充左边界 (条件判断)：类似地，如果此时 left <= right（确保至少还有一列未被完全覆盖），则在当前定义的左边界 left 列，从新的 bottom 行反向遍历到 top 行，将 matrix[i][left] 依次赋值为 num，并且 num 自增 1。完成这一列填充后，左边界向右收缩，即 left 增加 1。
重复直到填满：循环回到步骤2，继续以上四个方向的填充，直到 left > right 或 top > bottom，表示整个矩阵已经按照螺旋顺序填充完毕。此时，返回生成的 matrix 即可。

复杂度分析

时间复杂度：该算法需要填充 n x n 矩阵中的每一个单元格，并且每个单元格只被访问和填充一次。因此，总的操作次数与矩阵中元素的总数 n² 成正比。所以，算法的时间复杂度为 O(n²)。
空间复杂度：算法需要创建一个 n x n 的二维数组来存储生成的螺旋矩阵。这个矩阵占用的空间是 n²。除了这个输出矩阵之外，我们还使用了一些辅助变量来存储边界（top, bottom, left, right）和当前的数字（num），这些变量占用的空间是常数级别的，即 O(1)。因此，如果将输出矩阵计入空间复杂度，则整体空间复杂度为 O(n²)；如果不考虑输出矩阵本身所占用的空间（因为它通常被认为是问题本身的必要输出），那么额外的空间复杂度为 O(1)。在通常的算法分析中，我们会将输出结构所占用的空间也计算在内，故空间复杂度为 O(n²)。

源码

核心代码模式

下面提供了使用 Java、Python、JavaScript 和 Go 四种主流编程语言实现的“螺旋矩阵 II”算法。每种实现都遵循了前述的模拟填充思路，并添加了必要的注释以帮助读者理解代码逻辑。

Java

class Solution {
    public int[][] generateMatrix(int n) {
        // 创建一个 n x n 的二维数组，并用 0 初始化
        int[][] matrix = new int[n][n];
        
        // 定义边界
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        
        // 当前要填充的数字
        int num = 1;
        
        // 循环填充，直到所有元素都被填充
        while (num <= n * n) {
            // 1. 从左到右填充上边界
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++; // 上边界下移
            
            // 2. 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--; // 右边界左移
            
            // 3. 从右到左填充下边界 (确保还有行可以填充)
            if (top <= bottom) { // 检查是否越界
                for (int i = right; i >= left; i--) {
                    matrix[bottom][i] = num++;
                }
                bottom--; // 下边界上移
            }
            
            // 4. 从下到上填充左边界 (确保还有列可以填充)
            if (left <= right) { // 检查是否越界
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++; // 左边界右移
            }
        }
        
        return matrix;
    }
}

Python

def generateMatrix(n: int) -> list[list[int]]:
    # 创建一个 n x n 的二维列表，并用 0 初始化
    matrix = [[0] * n for _ in range(n)]
    
    # 定义边界
    top, bottom = 0, n - 1
    left, right = 0, n - 1
    
    # 当前要填充的数字
    num = 1
    
    # 循环填充，直到所有元素都被填充
    while num <= n * n:
        # 1. 从左到右填充上边界
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1 # 上边界下移
        
        # 2. 从上到下填充右边界
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1 # 右边界左移
        
        # 3. 从右到左填充下边界 (确保还有行可以填充)
        if top <= bottom: # 检查是否越界
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1 # 下边界上移
            
        # 4. 从下到上填充左边界 (确保还有列可以填充)
        if left <= right: # 检查是否越界
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1 # 左边界右移
            
    return matrix

JavaScript

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    // 创建一个 n x n 的二维数组，并用 0 初始化
    const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
    
    // 定义边界
    let top = 0, bottom = n - 1;
    let left = 0, right = n - 1;
    
    // 当前要填充的数字
    let num = 1;
    
    // 循环填充，直到所有元素都被填充
    while (num <= n * n) {
        // 1. 从左到右填充上边界
        for (let i = left; i <= right; i++) {
            matrix[top][i] = num++;
        }
        top++; // 上边界下移
        
        // 2. 从上到下填充右边界
        for (let i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--; // 右边界左移
        
        // 3. 从右到左填充下边界 (确保还有行可以填充)
        if (top <= bottom) { // 检查是否越界
            for (let i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--; // 下边界上移
        }
        
        // 4. 从下到上填充左边界 (确保还有列可以填充)
        if (left <= right) { // 检查是否越界
            for (let i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++; // 左边界右移
        }
    }
    
    return matrix;
};

func generateMatrix(n int) [][]int {
    // 创建一个 n x n 的二维切片，并用 0 初始化
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    
    // 定义边界
    top, bottom := 0, n-1
    left, right := 0, n-1
    
    // 当前要填充的数字
    num := 1
    
    // 循环填充，直到所有元素都被填充
    for num <= n*n {
        // 1. 从左到右填充上边界
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++ // 上边界下移
        
        // 2. 从上到下填充右边界
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right-- // 右边界左移
        
        // 3. 从右到左填充下边界 (确保还有行可以填充)
        if top <= bottom { // 检查是否越界
            for i := right; i >= left; i-- {
                matrix[bottom][i] = num
                num++
            }
            bottom-- // 下边界上移
        }
        
        // 4. 从下到上填充左边界 (确保还有列可以填充)
        if left <= right { // 检查是否越界
            for i := bottom; i >= top; i-- {
                matrix[i][left] = num
                num++
            }
            left++ // 左边界右移
        }
    }
    
    return matrix
}

面试可能会问的问题

该算法的核心思想是什么？ 面试官希望了解你对问题本质的理解。核心思想是模拟螺旋路径填充数字，通过维护四个边界（上、下、左、右）并逐步向内收缩，同时按照顺时针方向（右、下、左、上）依次填充数字。
为什么选择这种解法而不是其他方法？ 对于生成螺旋矩阵这类问题，模拟法是最直观且易于理解的。其他方法，如基于数学模式的直接计算每个位置的数字，可能会更复杂且难以推广。模拟法虽然步骤稍多，但逻辑清晰，边界处理也相对明确。
如果输入数据规模扩大，例如 n 变得非常大，算法的表现如何？ 算法的时间复杂度和空间复杂度都是 O(n²)。如果 n 变得非常大，例如 n=10000，那么 n² 就是 10^8，这可能导致内存不足（需要存储 n x n 的矩阵）和执行超时。需要向面试官说明在实际应用中，对于如此大规模的输入，可能需要考虑分布式处理或者优化存储方式，但这超出了本题常规解法的范畴。
是否可以进一步优化时间或空间复杂度？ 对于这个问题，时间复杂度 O(n²) 是最优的，因为我们必须填充 n² 个元素。空间复杂度 O(n²) 也是必需的，因为我们需要返回一个 n x n 的矩阵。如果不考虑输出矩阵本身，辅助空间复杂度是 O(1)，这已经是最优的了。因此，在此问题设定下，进一步优化的空间很小。
如果将某个条件修改，例如从逆时针开始填充，或者从右下角开始填充，算法需要做哪些调整？ 这个问题考察的是算法的灵活性和对边界控制的理解。如果改为逆时针填充，填充顺序会变为上、左、下、右，或者其他相应的调整，边界更新的逻辑也需要相应改变。如果从右下角开始，初始的 num 仍然是 1，但起始填充位置和方向会完全不同，边界的初始值和更新逻辑也需要重新设计。关键在于调整填充方向的顺序和边界收缩的逻辑。
如何验证算法的正确性？是否可以手动编写测试用例？ 验证算法正确性可以通过多种方式：
1. 手动模拟：对于较小的 n (如 n=1, 2, 3, 4)，可以手动模拟填充过程，与代码输出结果进行比对。
2. 边界条件测试：测试 n=1 (最小情况) 和 n=20 (题目给定的最大情况)。
3. 属性检查：检查生成的矩阵是否确实包含了从 1 到 n² 的所有数字，且每个数字只出现一次。检查最终矩阵的维度是否为 n x n。
4. 逻辑推演：仔细检查代码中边界更新、循环条件以及填充方向的逻辑是否与预期一致。可以手动编写测试用例，例如：
- n = 1，预期输出 [[1]]
- n = 2，预期输出 [[1,2],[4,3]]
- n = 3，预期输出 [[1,2,3],[8,9,4],[7,6,5]] 通过这些测试用例可以有效地验证算法的正确性。

数组

哈希表

链表

动态规划

螺旋矩阵

引言

题目标签

审题

解析

思路概述

算法步骤

复杂度分析

源码

核心代码模式

面试可能会问的问题