LeetCode Spiral Matrix II 螺旋矩陣生成算法解析

LeetCode Spiral Matrix II 題目解析

給定一個正整數 n，生成一個包含 1 到 n² 所有元素的 n×n 矩陣，元素按順時針螺旋順序填充。例如 n=3 時，輸出矩陣為：

[ [ 1, 2, 3 ],
  [ 8, 9, 4 ],
  [ 7, 6, 5 ] ]

遞歸分層填充法

採用遞歸思想，將矩陣視為同心層結構。每一層包含四條邊：頂邊從左到右、右邊從上到下、底邊從右到左、左邊從下到上。遞歸終止條件為層數超過中心點，奇數階矩陣中心單獨處理。

Java 代碼實現

public class Solution {
    int[][] res;
    int seq = 1;
    
    public int[][] generateMatrix(int n) {
        res = new int[n][n];
        help(n, 0);
        return res;
    }
    
    private void help(int n, int step) {
        if (step > n / 2) return;
        if (step == n / 2 && n % 2 != 0) {
            res[n / 2][n / 2] = seq++;
            return;
        }
        for (int i = step; i < n - step - 1; i++) res[step][i] = seq++;
        for (int i = step; i < n - step - 1; i++) res[i][n - step - 1] = seq++;
        for (int i = n - step - 1; i > step; i--) res[n - step - 1][i] = seq++;
        for (int i = n - step - 1; i > step; i--) res[i][step] = seq++;
        help(n, ++step);
    }
}

複雜度分析

• 時間複雜度：O(n²)，需填充 n² 個元素
• 空間複雜度：O(n²)，輸出矩陣佔用空間；遞歸棧深度 O(n)