Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 20

解题思路

这道题要求按螺旋顺序填充矩阵，核心思路是按层遍历。

解法分析

主要思路： 从外层到内层，逐层填充矩阵。每层按照"右→下→左→上"的顺序填充。

具体步骤：

  1. 定义四个边界：top、bottom、left、right
  2. 按照顺时针方向填充：
    • 从左到右填充上边界
    • 从上到下填充右边界
    • 从右到左填充下边界
    • 从下到上填充左边界
  3. 每完成一个方向的填充，相应收缩边界
  4. 重复直到所有位置都被填充

边界控制技巧： 使用四个变量控制边界，每次填充完一行或一列后立即更新边界，避免重复填充。

这种方法时间复杂度为 O(n²)，空间复杂度为 O(1)（不计算结果矩阵），是最优解法。

代码实现

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n));
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        
        while (top <= bottom && left <= right) {
            // 从左到右填充上边界
            for (int j = left; j <= right; j++) {
                matrix[top][j] = num++;
            }
            top++;
            
            // 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            // 从右到左填充下边界
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    matrix[bottom][j] = num++;
                }
                bottom--;
            }
            
            // 从下到上填充左边界
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;
            }
        }
        
        return matrix;
    }
};

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        num = 1
        
        while top <= bottom and left <= right:
            # 从左到右填充上边界
            for j in range(left, right + 1):
                matrix[top][j] = num
                num += 1
            top += 1
            
            # 从上到下填充右边界
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1
            
            # 从右到左填充下边界
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    matrix[bottom][j] = num
                    num += 1
                bottom -= 1
            
            # 从下到上填充左边界
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    matrix[i][left] = num
                    num += 1
                left += 1
        
        return matrix

public class Solution {
    public int[][] GenerateMatrix(int n) {
        int[][] matrix = new int[n][];
        for (int i = 0; i < n; i++) {
            matrix[i] = new int[n];
        }
        
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        
        while (top <= bottom && left <= right) {
            // 从左到右填充上边界
            for (int j = left; j <= right; j++) {
                matrix[top][j] = num++;
            }
            top++;
            
            // 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            // 从右到左填充下边界
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    matrix[bottom][j] = num++;
                }
                bottom--;
            }
            
            // 从下到上填充左边界
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;
            }
        }
        
        return matrix;
    }
}

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    const matrix = Array.from({length: n}, () => Array(n).fill(0));
    let top = 0, bottom = n - 1, left = 0, right = n - 1;
    let num = 1;
    
    while (top <= bottom && left <= right) {
        // 从左到右填充上边界
        for (let j = left; j <= right; j++) {
            matrix[top][j] = num++;
        }
        top++;
        
        // 从上到下填充右边界
        for (let i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;
        
        // 从右到左填充下边界
        if (top <= bottom) {
            for (let j = right; j >= left; j--) {
                matrix[bottom][j] = num++;
            }
            bottom--;
        }
        
        // 从下到上填充左边界
        if (left <= right) {
            for (let i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
    }
    
    return matrix;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要填充 n×n 矩阵中的每个元素
空间复杂度O(1)除了结果矩阵外，只使用常数额外空间

相关题目