59. 螺旋矩阵 II

【题目】

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

示例 1：

image.png

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

示例 2：

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

提示：

• 1 <= n <= 20

【题目解析】

解析方法

1. 初始化一个 n×nn×n 的矩阵，填充为 0。
2. 设置起始点位置 (x, y)，初始为 (0, 0)。
3. 按螺旋顺序填充矩阵，直到填充所有数字 。
4. 更新填充方向和边界，以确保正确填充每一圈。

class Solution:
    def generateMatrix(self, n: int) -> [[int]]:
        # 初始化矩阵
        matrix = [[0] * n for _ in range(n)]
        # 设置初始值
        num, max_num = 1, n * n
        left, right, top, bottom = 0, n - 1, 0, n - 1
        
        while num <= max_num:
            # 从左到右填充上层
            for y in range(left, right + 1):
                matrix[top][y] = num
                num += 1
            top += 1
            
            # 从上到下填充右侧
            for x in range(top, bottom + 1):
                matrix[x][right] = num
                num += 1
            right -= 1
            
            # 从右到左填充下层
            for y in range(right, left - 1, -1):
                matrix[bottom][y] = num
                num += 1
            bottom -= 1
            
            # 从下到上填充左侧
            for x in range(bottom, top - 1, -1):
                matrix[x][left] = num
                num += 1
            left += 1
            
        return matrix

执行效率

image.png

【总结】

适用问题类型

• 生成特定模式的矩阵问题，尤其是需要按矩阵边界顺时针或逆时针填充元素的场景。
• 任何需要按照一定规则逐步构建二维数据结构的问题。

解决算法

• 算法描述：从矩阵的外层开始，按顺时针方向逐层填充矩阵元素，直到所有元素被填充。每次填充完矩阵的一层（四条边），向内缩进，继续填充下一层，直到完成。

算法特点

• 直观且易于实现：这种方法模拟了填充过程，逻辑清晰。
• 灵活性高：容易根据需要调整填充的方向（顺时针或逆时针）和模式。

时间复杂度与空间复杂度

• 时间复杂度：O(n^2)，因为需要遍历矩阵中的每个元素一次。
• 空间复杂度：O(1)，除了需要返回的结果矩阵外，算法本身只使用了常数空间。

实践意义

• 算法思维训练：模拟法是解决复杂问题的一个重要思维方式，能够帮助理解和分析问题的具体过程。
• 编程技巧提升：通过实现这种算法，可以提升对循环、条件判断以及边界控制等编程基本要素的掌握。
• 适用于多种场景：模拟法不仅限于生成螺旋矩阵，还可以扩展到其他需要按特定规则操作数据的问题，如游戏开发中的地图生成、图形界面的绘制等。

总的来说，模拟法在处理生成螺旋矩阵等具有特定填充规律的问题时，既高效又具有较好的可读性和可维护性，是一种值得学习和掌握的算法设计思想。

题目链接

螺旋矩阵 II