給定一個 m x n 的矩陣
matrix，按照螺旋順序（順時針由外到內）回傳矩陣中所有元素。
Example:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]
Intuition
TIP
核心思路：用四個邊界指標（top, bottom, left, right）模擬螺旋遍歷，每走完一邊就收縮對應邊界。
- 螺旋遍歷的順序：右 -> 下 -> 左 -> 上，重複直到所有元素都被訪問
- 用四個邊界變數控制遍歷範圍，走完一邊就往內縮一層
- 注意收縮後要檢查邊界是否仍有效，避免重複遍歷
Approaches
1. Direction Simulation + Marking — O(m * n) / O(m * n)
- Idea: 維護當前方向和已訪問標記，碰到邊界或已訪問的格子就轉向
- Time:
O(m * n)- 每個元素訪問一次 - Space:
O(m * n)- 需要已訪問標記矩陣
class Solution {
fun spiralOrder(matrix: Array<IntArray>): List<Int> {
val m = matrix.size
val n = matrix[0].size
val visited = Array(m) { BooleanArray(n) }
val result = mutableListOf<Int>()
val dr = intArrayOf(0, 1, 0, -1) // 右、下、左、上
val dc = intArrayOf(1, 0, -1, 0)
var r = 0
var c = 0
var dir = 0
for (i in 0 until m * n) {
result.add(matrix[r][c])
visited[r][c] = true
val nr = r + dr[dir]
val nc = c + dc[dir]
if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
dir = (dir + 1) % 4
}
r += dr[dir]
c += dc[dir]
}
return result
}
}⭐ 2. Four-Boundary Shrinking — O(m * n) / O(1)
- Idea: 用 top, bottom, left, right 四個邊界依序遍歷上行、右列、下行、左列，每走完一邊就收縮邊界
- Time:
O(m * n)- 每個元素訪問一次 - Space:
O(1)- 不含輸出
class Solution {
fun spiralOrder(matrix: Array<IntArray>): List<Int> {
val result = mutableListOf<Int>()
var top = 0
var bottom = matrix.size - 1
var left = 0
var right = matrix[0].size - 1
while (top <= bottom && left <= right) {
// 上行：左到右
for (j in left..right) result.add(matrix[top][j])
top++
// 右列：上到下
for (i in top..bottom) result.add(matrix[i][right])
right--
// 下行：右到左
if (top <= bottom) {
for (j in right downTo left) result.add(matrix[bottom][j])
bottom--
}
// 左列：下到上
if (left <= right) {
for (i in bottom downTo top) result.add(matrix[i][left])
left++
}
}
return result
}
}WARNING
走完上行和右列後，必須檢查 top <= bottom 和 left <= right，因為對於單行或單列的情況，可能已經走完所有元素了。
🔑 Takeaways
- Pattern: 邊界收縮法是螺旋遍歷類問題的標準模板
- Key trick: 記住四步循環（右下左上）+ 邊界檢查，可直接套用到 Spiral Matrix II 等變體題