LeetCode 54 Spiral Matrix：順時針螺旋遍歷矩陣

題目大意

給 m×n 矩陣，按順時針螺旋順序輸出所有元素。例如 [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]。

方法一：層層剝洋蔥（遞歸/迭代）

• 定義四個邊界：`top=0, bottom=m-1, left=0, right=n-1`。
• 按順序：左→右 (top行)、上→下 (right列)、右→左 (bottom行)、下→上 (left列)。
• 每完成一圈，邊界向內收縮：`top++, bottom--, left++, right--`。
• 終止條件：`top > bottom` 或 `left > right`。
• 注意單行/單列情況避免重複遍歷。

代碼（迭代版）

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        vector res;
        if (matrix.empty()) return res;
        int m = matrix.size(), n = matrix[0].size();
        int top = 0, bottom = m-1, left = 0, right = n-1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; ++j) res.push_back(matrix[top][j]);
            if (++top > bottom) break;
            for (int i = top; i <= bottom; ++i) res.push_back(matrix[i][right]);
            if (--right < left) break;
            for (int j = right; j >= left; --j) res.push_back(matrix[bottom][j]);
            if (--bottom < top) break;
            for (int i = bottom; i >= top; --i) res.push_back(matrix[i][left]);
            ++left;
        }
        return res;
    }
};

方法二：DFS + 訪問標記（通用但較慢）

• 方向順序：右、下、左、上。
• 嘗試當前方向，若越界或已訪問，順時針轉向。
• 用 `visited[m][n]` 標記。

複雜度

• 時間：O(mn)，每個元素訪問一次。
• 空間：O(1) 額外（不含輸出），或 O(mn) 訪問標記。

總結

Spiral Matrix 是經典的矩陣遍歷題。**邊界收縮法** 代碼最簡潔、無額外空間、邏輯清晰，是面試首選寫法。DFS 法通用性強（適用於不規則螺旋），但常數較大。