LeetCode 59. 螺旋矩阵 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：边界收缩模拟（推荐）
2. 解法二：计数终止模拟
相似题目

题目描述

✅ 59. 螺旋矩阵 II

考察公司：小米

思路分析

解法一：边界收缩模拟（推荐）

核心思路：

维护四个边界 top、bottom、left、right，初始分别指向矩阵的上、下、左、右边缘。

每一圈按「左→右、上→下、右→左、下→上」四个方向依次填数，填完一条边后收缩对应边界。

用 top <= bottom && left <= right 作为循环条件，避免重复填写已处理的行或列。

填右→左和下→上时，需额外判断边界是否仍然有效，防止奇数阶矩阵中心行/列被重复填充。

复杂度分析：

时间复杂度：O(n²)，其中 n 为矩阵边长，需填充 n² 个元素

空间复杂度：O(1)，不计结果数组

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        // 定义四个边界
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;

        while (top <= bottom && left <= right) {
            // 从左到右填充 top 行
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;

            // 从上到下填充 right 列
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;

            // 从右到左填充 bottom 行（需判断边界仍有效）
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    matrix[bottom][i] = num++;
                }
                bottom--;
            }

            // 从下到上填充 left 列（需判断边界仍有效）
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;
            }
        }

        return matrix;
    }
}

func generateMatrix(n int) [][]int {
    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 top <= bottom && left <= right {
        // 从左到右填充 top 行
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++

        // 从上到下填充 right 列
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--

        // 从右到左填充 bottom 行（需判断边界仍有效）
        if top <= bottom {
            for i := right; i >= left; i-- {
                matrix[bottom][i] = num
                num++
            }
            bottom--
        }

        // 从下到上填充 left 列（需判断边界仍有效）
        if left <= right {
            for i := bottom; i >= top; i-- {
                matrix[i][left] = num
                num++
            }
            left++
        }
    }

    return matrix
}

解法二：计数终止模拟

核心思路：

同样维护四个边界，但以 num <= n*n 作为循环终止条件，不再需要对回填方向做额外边界判断。

每轮按顺序填完四个方向后收缩对应边界，当 num 超过 n² 时自然退出循环。

适合 n 较小时快速实现，代码略简洁，但不如解法一在边界处理上显式清晰。

复杂度分析：

时间复杂度：O(n²)，其中 n 为矩阵边长，需填充 n² 个元素

空间复杂度：O(1)，不计结果数组

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;

        // 以填充数量为循环终止条件
        while (num <= n * n) {
            // 从左到右填一行
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;

            // 从上到下填一列
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;

            // 从右到左填一行
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;

            // 从下到上填一列
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }

        return matrix;
    }
}

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }

    top, bottom, left, right := 0, n-1, 0, n-1
    num := 1

    // 以填充数量为循环终止条件
    for num <= n*n {
        // 从左到右填一行
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++

        // 从上到下填一列
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--

        // 从右到左填一行
        for i := right; i >= left; i-- {
            matrix[bottom][i] = num
            num++
        }
        bottom--

        // 从下到上填一列
        for i := bottom; i >= top; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }

    return matrix
}

相似题目

题目	难度	考察点
54. 螺旋矩阵	中等	矩阵模拟、边界收缩
885. 螺旋矩阵 III	中等	矩阵模拟、方向数组
2326. 螺旋矩阵 IV	中等	矩阵模拟、链表填充
498. 对角线遍历	中等	矩阵模拟、方向控制
剑指 Offer 29. 顺时针打印矩阵	简单	矩阵模拟、边界收缩
48. 旋转图像	中等	矩阵原地变换

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/80898555