LeetCode 筆記：螺旋矩陣 - 邊界收縮法遍歷輸出

問題描述

給定 m x n 矩陣，按順時針螺旋順序返回所有元素。

範例：

輸入: [[1,2,3],
       [4,5,6],
       [7,8,9]]
輸出: [1,2,3,6,9,8,7,4,5]

解題思路：四邊界收縮

維護四個邊界變數：

• top、bottom：行邊界
• left、right：列邊界

按順序遍歷：左→右（頂行）、上→下（右列）、右→左（底行）、下→上（左列），每完成一邊就收縮對應邊界，直到邊界交錯。

C++ 實現

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        vector result;
        if (matrix.empty()) return result;
        
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        
        while (true) {
            // 左 → 右：頂行
            for (int j = left; j <= right; ++j)
                result.push_back(matrix[top][j]);
            if (++top > bottom) break;
            
            // 上 → 下：右列
            for (int i = top; i <= bottom; ++i)
                result.push_back(matrix[i][right]);
            if (left > --right) break;
            
            // 右 → 左：底行
            for (int j = right; j >= left; --j)
                result.push_back(matrix[bottom][j]);
            if (top > --bottom) break;
            
            // 下 → 上：左列
            for (int i = bottom; i >= top; --i)
                result.push_back(matrix[i][left]);
            if (++left > right) break;
        }
        return result;
    }
};

執行過程圖解

以 3×3 矩陣為例：

關鍵點總結

1. 邊界更新順序：遍歷完一邊立即更新對應邊界，再檢查是否越界
2. 終止條件：每次遍歷後檢查 top > bottom 或 left > right
3. 邊界情況：單行、單列、空矩陣均能正確處理
4. 時間空間：O(mn) 時間，O(1) 額外空間（不含輸出）

變體延伸

• 螺旋矩陣 II：給定 n，生成 n×n 螺旋矩陣（填充而非讀取）
• 螺旋矩陣 III：在無限網格上螺旋行走，記錄經過指定範圍內的座標