LeetCode 59. Spiral Matrix II：按層螺旋填充矩陣 (邊界收縮法)

題目

給定正整數 n，生成 n×n 矩陣，元素 1 到 n² 按順時針螺旋順序填充。例 n=3：
[[1,2,3],[8,9,4],[7,6,5]]

邊界收縮法 (最直觀)

維護四個邊界：top, bottom, left, right。按「左→右、上→下、右→左、下→上」四方向填充，每完成一方向收縮對應邊界，直到 top>bottom 或 left>right。

C++ 實現

class Solution {
public:
    vector> generateMatrix(int n) {
        vector> mat(n, vector(n));
        int top=0, bottom=n-1, left=0, right=n-1;
        int val = 1, target = n*n;
        while (val <= target) {
            for (int c=left; c<=right; ++c) mat[top][c] = val++;
            if (++top > bottom) break;
            for (int r=top; r<=bottom; ++r) mat[r][right] = val++;
            if (--right < left) break;
            for (int c=right; c>=left; --c) mat[bottom][c] = val++;
            if (--bottom < top) break;
            for (int r=bottom; r>=top; --r) mat[r][left] = val++;
            ++left;
        }
        return mat;
    }
};

關鍵點

• 每個方向填完立即檢查邊界是否交叉，避免重複填充中心點 (奇數 n 時)。
• 時間 O(n²)，空間 O(1) (不計輸出)。
• 方向順序固定：右 → 下 → 左 → 上。