題目描述
題目要求
給定一個 m x n 的矩陣 matrix，請按照 螺旋順序（spiral order） 返回矩陣中的所有元素。
限制條件
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
雖然 m 和 n 只有 最多 10，但我們仍希望找到高效的解法。
範例
範例 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來標記矩陣的邊界，每次遍歷完一條邊就縮小範圍。 - 時間複雜度：O(m * n)，因為每個元素都會被訪問一次。
思路 2：使用方向變換
- 使用 方向變量
[(0,1), (1,0), (0,-1), (-1,0)]來控制遍歷順序，遇到邊界時切換方向。 - 時間複雜度：O(m * n)，但要額外處理訪問過的元素。
解法一：模擬螺旋順序
思路
- 設定
top,bottom,left,right來標記矩陣範圍。 - 從
left → right，top → bottom，right → left，bottom → top依序收縮範圍。 - 當
top <= bottom且left <= right時繼續遍歷。
程式碼
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
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 += 1
return result
時間與空間複雜度
- 時間複雜度：O(m * n)（遍歷所有元素一次）
- 空間複雜度：O(1)（只使用額外的
result陣列）
解法二：使用方向變換
思路
- 使用
directions = [(0,1), (1,0), (0,-1), (-1,0)]來控制方向變化。 - 用
visited紀錄哪些元素已經走過，遇到邊界或已訪問的格子就改變方向。
程式碼
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
m, n = len(matrix), len(matrix[0])
visited = [[False] * n for _ in range(m)]
result = []
directions = [(0,1), (1,0), (0,-1), (-1,0)] # 右, 下, 左, 上
x, y, d = 0, 0, 0 # 起始位置 & 方向索引
for _ in range(m * n):
result.append(matrix[x][y])
visited[x][y] = True
new_x, new_y = x + directions[d][0], y + directions[d][1]
if 0 <= new_x < m and 0 <= new_y < n and not visited[new_x][new_y]:
x, y = new_x, new_y
else:
d = (d + 1) % 4 # 改變方向
x, y = x + directions[d][0], y + directions[d][1]
return result
時間與空間複雜度
- 時間複雜度：O(m * n)（每個元素遍歷一次）
- 空間複雜度：O(m * n)（使用
visited紀錄已訪問的格子）
結論
這題相較之下適合用 模擬螺旋順序 來解，因為它的 O(1) 空間複雜度，不需要額外儲存空間。
