跳转至

Spiral Matrix (螺旋矩陣) 🟡 Medium

📌 LeetCode #54 — 題目連結 | NeetCode 解說

1. 🧐 Problem Dissection (釐清問題)

給定一個 m x n 的矩陣 matrix。 請按照 順時針螺旋順序 (Spiral Order)，回傳矩陣中的所有元素。

  • Input: 

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

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

  • Input: 

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

  • Output: [1,2,3,4,8,12,11,10,9,5,6,7]

  • Constraints:
    • \(m, n\) up to 10.
    • Total elements up to 100.

2. 🐢 Brute Force Approach (暴力解)

這沒有特別的暴力解，主要是模擬。 這是一個模擬題，重點在於邊界控制。

3. 💡 The "Aha!" Moment (優化)

Simulation with Boundaries (Layer-by-Layer): 維護四個邊界：

  • top
  • bottom
  • left
  • right

順序：

  1. Left to Right: matrix[top][left...right], then top++.
  2. Top to Bottom: matrix[top...bottom][right], then right--.
  3. Right to Left: matrix[bottom][right...left], then bottom--.
    • Check: 必須確保 top <= bottom，否則會重複遍歷。
  4. Bottom to Top: matrix[bottom...top][left], then left++.
    • Check: 必須確保 left <= right。

Loop Condition: while (top <= bottom && left <= right)。

🎬 Visualization (演算法視覺化)

⤢ 全螢幕開啟視覺化

4. 💻 Implementation (程式碼)

Approach: Simulation

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};

        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> result;

        int top = 0;
        int bottom = m - 1;
        int left = 0;
        int right = n - 1;

        while (top <= bottom && left <= right) {
            // 1. Left to Right
            for (int j = left; j <= right; j++) {
                result.push_back(matrix[top][j]);
            }
            top++; // Shrink top boundary

            // 2. Top to Bottom
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--; // Shrink right boundary

            // Check if done after shrinking
            if (top > bottom || left > right) break;

            // 3. Right to Left
            for (int j = right; j >= left; j--) {
                result.push_back(matrix[bottom][j]);
            }
            bottom--; // Shrink bottom boundary

            // 4. Bottom to Top
            for (int i = bottom; i >= top; i--) {
                result.push_back(matrix[i][left]);
            }
            left++; // Shrink left boundary
        }

        return result;
    }
};

Python Reference

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        left, right = 0, len(matrix[0])
        top, bottom = 0, len(matrix)

        while left < right and top < bottom:
            # get every i in the top row
            for i in range(left, right):
                res.append(matrix[top][i])
            top += 1

            # get every i in the right col
            for i in range(top, bottom):
                res.append(matrix[i][right - 1])
            right -= 1

            if not (left < right and top < bottom):
                break

            # get every i in the bottom row
            for i in range(right - 1, left - 1, -1):
                res.append(matrix[bottom - 1][i])
            bottom -= 1

            # get every i in the left col
            for i in range(bottom - 1, top - 1, -1):
                res.append(matrix[i][left])
            left += 1

        return res

5. 📝 Detailed Code Comments (詳細註解)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};

        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> result;

        // 定義四個邊界
        int top = 0;
        int bottom = m - 1;
        int left = 0;
        int right = n - 1;

        // 當邊界還沒有交錯時，繼續遍歷
        while (top <= bottom && left <= right) {
            // 1. 從左到右 (遍歷上邊界)
            for (int j = left; j <= right; j++) {
                result.push_back(matrix[top][j]);
            }
            top++; // 上邊界向下收縮

            // 2. 從上到下 (遍歷右邊界)
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--; // 右邊界向左收縮

            // 關鍵檢查：
            // 在上縮和右縮之後，可能會導致 top > bottom 或 left > right
            // 例如單行矩陣，遍歷完第一步 top++ 後就結束了
            // 如果不檢查，後面的步驟會重複遍歷或越界
            if (top > bottom || left > right) break;

            // 3. 從右到左 (遍歷下邊界)
            for (int j = right; j >= left; j--) {
                result.push_back(matrix[bottom][j]);
            }
            bottom--; // 下邊界向上收縮

            // 4. 從下到上 (遍歷左邊界)
            for (int i = bottom; i >= top; i--) {
                result.push_back(matrix[i][left]);
            }
            left++; // 左邊界向右收縮
        }

        return result;
    }
};

6. 📊 Rigorous Complexity Analysis (複雜度分析)

  • Time Complexity: \(O(M \times N)\)
    • Each element is visited exactly once.
  • Space Complexity: \(O(1)\)
    • If not counting the output array.

7. 💼 Interview Tips (面試技巧)

🎯 Follow-up 問題

面試官可能會問的延伸問題：

  • 你會如何處理更大的輸入？
  • 有沒有更好的空間複雜度？

🚩 常見錯誤 (Red Flags)

避免這些會讓面試官扣分的錯誤：

  • ⚠️ 沒有考慮邊界條件
  • ⚠️ 未討論複雜度

✨ 加分項 (Bonus Points)

這些會讓你脫穎而出：

  • 💎 主動討論 trade-offs
  • 💎 提供多種解法比較

站內相關

進階挑戰