54. Spiral Matrix

Medium

Description

給定一個 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#

核心思路：用四個邊界指標（top, bottom, left, right）模擬螺旋遍歷，每走完一邊就收縮對應邊界。

螺旋遍歷的順序：右 -> 下 -> 左 -> 上，重複直到所有元素都被訪問
用四個邊界變數控制遍歷範圍，走完一邊就往內縮一層
注意收縮後要檢查邊界是否仍有效，避免重複遍歷

Approaches#

1: 方向模擬 + 標記#

概念: 維護當前方向和已訪問標記，碰到邊界或已訪問的格子就轉向
時間複雜度: O(m * n) - 每個元素訪問一次
空間複雜度: 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: 四邊界收縮#

概念: 用 top, bottom, left, right 四個邊界依序遍歷上行、右列、下行、左列，每走完一邊就收縮邊界
時間複雜度: O(m * n) - 每個元素訪問一次
空間複雜度: 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
    }
}

走完上行和右列後，必須檢查 top <= bottom 和 left <= right，因為對於單行或單列的情況，可能已經走完所有元素了。

🔑 Takeaways#

Pattern: 邊界收縮法是螺旋遍歷類問題的標準模板
關鍵技巧: 記住四步循環（右下左上）+ 邊界檢查，可直接套用到 Spiral Matrix II 等變體題