59. 螺旋矩阵 II

题目描述

输入正整数 n，构造一个 n x n 的矩阵。

从左上角开始，按顺时针方向由外向内一圈圈地填数：先向右填满第一行，再向下、向左、向上，依此类推。填入的数从 1 开始，每次加 1，直到 n^2。

返回填好的矩阵。

示例 1

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

解释：外圈依次填 1 到 8，中心填 9。

示例 2

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

数据范围

1 <= n <= 20

解题思路：方向模拟

模拟一个按“右、下、左、上”顺序转向的小人：从左上角出发，依次写入 1, 2, …, n²。每写完一格先试探下一格；若越界或已被填过，就顺时针转 90 度，再前进。

为什么正确

已填的格子恰好是螺旋路径的前 num 个位置；未填格子的值都是 0，所以“下一格为 0”就代表可以继续直走。

复杂度分析

时间 O(n²)，每个格子只写一次；除答案外空间 O(1)。

易错点

判断转向要同时检查越界和“已填过”，只检查越界会在第二圈覆盖第一圈的数。转向后要重新计算下一格，而不是继续沿用转向前算出的位置。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        i = j = d = 0
        for num in range(1, n * n + 1):
            mat[i][j] = num
            ni, nj = i + dirs[d][0], j + dirs[d][1]
            if not (0 <= ni < n and 0 <= nj < n and mat[ni][nj] == 0):
                d = (d + 1) % 4
            i, j = i + dirs[d][0], j + dirs[d][1]
        return mat

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] mat = new int[n][n];
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int i = 0, j = 0, d = 0;
        for (int num = 1; num <= n * n; num++) {
            mat[i][j] = num;
            int ni = i + dirs[d][0], nj = j + dirs[d][1];
            if (!(0 <= ni && ni < n && 0 <= nj && nj < n && mat[ni][nj] == 0)) {
                d = (d + 1) % 4;
            }
            i += dirs[d][0];
            j += dirs[d][1];
        }
        return mat;
    }
}

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int i = 0, j = 0, d = 0;
        for (int num = 1; num <= n * n; num++) {
            mat[i][j] = num;
            int ni = i + dirs[d][0], nj = j + dirs[d][1];
            if (!(0 <= ni && ni < n && 0 <= nj && nj < n && mat[ni][nj] == 0)) {
                d = (d + 1) % 4;
            }
            i += dirs[d][0];
            j += dirs[d][1];
        }
        return mat;
    }
};

func generateMatrix(n int) [][]int {
	mat := make([][]int, n)
	for k := range mat {
		mat[k] = make([]int, n)
	}
	dirs := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	i, j, d := 0, 0, 0
	for num := 1; num <= n*n; num++ {
		mat[i][j] = num
		ni, nj := i+dirs[d][0], j+dirs[d][1]
		if !(0 <= ni && ni < n && 0 <= nj && nj < n && mat[ni][nj] == 0) {
			d = (d + 1) % 4
		}
		i, j = i+dirs[d][0], j+dirs[d][1]
	}
	return mat
}

var generateMatrix = function(n) {
    const mat = Array.from({ length: n }, () => new Array(n).fill(0));
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let i = 0, j = 0, d = 0;
    for (let num = 1; num <= n * n; num++) {
        mat[i][j] = num;
        const ni = i + dirs[d][0], nj = j + dirs[d][1];
        if (!(0 <= ni && ni < n && 0 <= nj && nj < n && mat[ni][nj] === 0)) {
            d = (d + 1) % 4;
        }
        i += dirs[d][0];
        j += dirs[d][1];
    }
    return mat;
};

function generateMatrix(n: number): number[][] {
    const mat: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let i = 0, j = 0, d = 0;
    for (let num = 1; num <= n * n; num++) {
        mat[i][j] = num;
        const ni = i + dirs[d][0], nj = j + dirs[d][1];
        if (!(0 <= ni && ni < n && 0 <= nj && nj < n && mat[ni][nj] === 0)) {
            d = (d + 1) % 4;
        }
        i += dirs[d][0];
        j += dirs[d][1];
    }
    return mat;
}

载入编辑器，自己跑一遍 →

其他解法

方向模拟靠“下一格越界或已填”来转向，代码短；按层填充靠四条边界控制范围，结构更清晰，两者复杂度相同。

解法 2：按层填充时间 O(n²)，空间 O(1)

维护 top、bottom、left、right 四条边界。每一圈依次填上边、右边、下边、左边，每填完一条边就把对应边界向内收缩一格。下边和左边在填之前检查边界仍然有效。

不需要读取矩阵判断格子是否填过，每条边是一个简单循环。需要注意收缩顺序和边界检查。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[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):
                mat[top][j] = num
                num += 1
            top += 1
            for i in range(top, bottom + 1):
                mat[i][right] = num
                num += 1
            right -= 1
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    mat[bottom][j] = num
                    num += 1
                bottom -= 1
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    mat[i][left] = num
                    num += 1
                left += 1
        return mat

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] mat = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1, num = 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) mat[top][j] = num++;
            top++;
            for (int i = top; i <= bottom; i++) mat[i][right] = num++;
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) mat[bottom][j] = num++;
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) mat[i][left] = num++;
                left++;
            }
        }
        return mat;
    }
}

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int top = 0, bottom = n - 1, left = 0, right = n - 1, num = 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) mat[top][j] = num++;
            top++;
            for (int i = top; i <= bottom; i++) mat[i][right] = num++;
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) mat[bottom][j] = num++;
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) mat[i][left] = num++;
                left++;
            }
        }
        return mat;
    }
};

func generateMatrix(n int) [][]int {
	mat := make([][]int, n)
	for i := range mat {
		mat[i] = make([]int, n)
	}
	top, bottom, left, right, num := 0, n-1, 0, n-1, 1
	for top <= bottom && left <= right {
		for j := left; j <= right; j++ {
			mat[top][j] = num
			num++
		}
		top++
		for i := top; i <= bottom; i++ {
			mat[i][right] = num
			num++
		}
		right--
		if top <= bottom {
			for j := right; j >= left; j-- {
				mat[bottom][j] = num
				num++
			}
			bottom--
		}
		if left <= right {
			for i := bottom; i >= top; i-- {
				mat[i][left] = num
				num++
			}
			left++
		}
	}
	return mat
}

var generateMatrix = function(n) {
    const mat = Array.from({ length: n }, () => Array(n).fill(0));
    let top = 0, bottom = n - 1, left = 0, right = n - 1, num = 1;
    while (top <= bottom && left <= right) {
        for (let j = left; j <= right; j++) mat[top][j] = num++;
        top++;
        for (let i = top; i <= bottom; i++) mat[i][right] = num++;
        right--;
        if (top <= bottom) {
            for (let j = right; j >= left; j--) mat[bottom][j] = num++;
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; i--) mat[i][left] = num++;
            left++;
        }
    }
    return mat;
};

function generateMatrix(n: number): number[][] {
    const mat: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    let top = 0, bottom = n - 1, left = 0, right = n - 1, num = 1;
    while (top <= bottom && left <= right) {
        for (let j = left; j <= right; j++) mat[top][j] = num++;
        top++;
        for (let i = top; i <= bottom; i++) mat[i][right] = num++;
        right--;
        if (top <= bottom) {
            for (let j = right; j >= left; j--) mat[bottom][j] = num++;
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; i--) mat[i][left] = num++;
            left++;
        }
    }
    return mat;
}

数学专题的其他题目

查看数学全部题目 →