LeetCode 熱題 100 | 54. 螺旋矩陣

大家好，今天我們來解決一道經典的算法題——螺旋矩陣。這道題在LeetCode上被標記為中等難度，要求我們按照順時針螺旋順序返回矩陣中的所有元素。下面我將詳細講解解題思路，并附上Python代碼實現。

---

問題描述

給定一個 m 行 n 列的矩陣 matrix，請按照順時針螺旋順序，返回矩陣中的所有元素。

示例1：

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

示例2：

輸入: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

---

解題思路

核心思想

1. 邊界模擬法：

   • 定義矩陣的四個邊界：上邊界 top、下邊界 bottom、左邊界 left、右邊界 right。
   • 按照順時針方向（右→下→左→上）依次遍歷矩陣的邊界，并不斷調整邊界。

2. 遍歷順序：

   • 從左到右遍歷上邊界，完成后上邊界下移。
   • 從上到下遍歷右邊界，完成后右邊界左移。
   • 從右到左遍歷下邊界，完成后下邊界上移。
   • 從下到上遍歷左邊界，完成后左邊界右移。

3. 終止條件：

   • 當所有元素都被遍歷時（即 top > bottom 或 left > right），停止遍歷。

---

Python代碼實現

def spiralOrder(matrix):if not matrix:return []top, bottom = 0, len(matrix) - 1left, right = 0, len(matrix[0]) - 1result = []while top <= bottom and left <= right:# 從左到右遍歷上邊界for i in range(left, right + 1):result.append(matrix[top][i])top += 1# 從上到下遍歷右邊界for i in range(top, bottom + 1):result.append(matrix[i][right])right -= 1# 檢查是否還有下邊界需要遍歷if top <= bottom:# 從右到左遍歷下邊界for i in range(right, left - 1, -1):result.append(matrix[bottom][i])bottom -= 1# 檢查是否還有左邊界需要遍歷if left <= right:# 從下到上遍歷左邊界for i in range(bottom, top - 1, -1):result.append(matrix[i][left])left += 1return result# 測試示例
matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
matrix2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]print(spiralOrder(matrix1))  # 輸出: [1,2,3,6,9,8,7,4,5]
print(spiralOrder(matrix2))  # 輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

---

代碼解析

1. 初始化邊界：

   • top 和 bottom 分別表示矩陣的上下邊界。
   • left 和 right 分別表示矩陣的左右邊界。

2. 順時針遍歷：

   • 從左到右：遍歷上邊界，完成后將 top 下移。
   • 從上到下：遍歷右邊界，完成后將 right 左移。
   • 從右到左：遍歷下邊界（需檢查 top <= bottom），完成后將 bottom 上移。
   • 從下到上：遍歷左邊界（需檢查 left <= right），完成后將 left 右移。

3. 終止條件：

   • 當 top > bottom 或 left > right 時，說明所有元素已被遍歷。

---

復雜度分析

• 時間復雜度：O(m × n)，其中 m 是矩陣的行數，n 是矩陣的列數。我們需要遍歷矩陣中的每個元素一次。
• 空間復雜度：O(1)，除了輸出結果外，只使用了常數個額外空間。

---

示例運行

示例1

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

示例2

輸入: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

---

進階：其他解法

方法一：遞歸法

def spiralOrder_recursive(matrix):if not matrix:return []result = []rows, cols = len(matrix), len(matrix[0])def helper(top, bottom, left, right):if top > bottom or left > right:return# 從左到右遍歷上邊界for i in range(left, right + 1):result.append(matrix[top][i])top += 1# 從上到下遍歷右邊界for i in range(top, bottom + 1):result.append(matrix[i][right])right -= 1# 檢查是否還有下邊界需要遍歷if top <= bottom:# 從右到左遍歷下邊界for i in range(right, left - 1, -1):result.append(matrix[bottom][i])bottom -= 1# 檢查是否還有左邊界需要遍歷if left <= right:# 從下到上遍歷左邊界for i in range(bottom, top - 1, -1):result.append(matrix[i][left])left += 1helper(top, bottom, left, right)helper(0, rows - 1, 0, cols - 1)return result

• 時間復雜度：O(m × n)
• 空間復雜度：O(min(m, n))，遞歸調用的棧空間。

---

總結

通過使用邊界模擬法，我們可以高效地按照順時針螺旋順序遍歷矩陣中的所有元素。這種方法直觀且易于實現，適合大多數場景。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！