> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/05_stack_queue/54.-spiral-matrix.md).

# 54. Spiral Matrix

<https://leetcode.com/problems/spiral-matrix/>

## solution

```python
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        start_col = 0
        start_row = 0
        n_col = len(matrix[0]) - 1
        n_row = len(matrix) - 1

        res = []  # [[0 for _ in range(n_row)] for _ in range(n_col)]

        while start_col <= n_col and start_row <= n_row:
            for i in range(start_col, n_col+1):
                res.append(matrix[start_row][i])
            start_row += 1

            for i in range(start_row, n_row+1):
                res.append(matrix[i][n_col])
            n_col -= 1

            if start_row <= n_row:
                for i in range(n_col, start_col - 1, -1):
                    res.append(matrix[n_row][i])
                n_row -= 1

            if start_col <= n_col:
                for i in range(n_row, start_row - 1, -1):
                    res.append(matrix[i][start_col])
                start_col += 1
        return res
```

时间复杂度：O()\
空间复杂度：O()

```python
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        n = len(matrix[0])

        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        row = col = dir_idx = 0
        res = []
        visited = set()

        for _ in range(m * n):
            res.append(matrix[row][col])
            visited.add((row, col))

            # 可能要换方向, 根据下面条件确定是否换
            next_row, next_col = row + dirs[dir_idx][0], col + dirs[dir_idx][1]

            if not 0 <= next_row < m or not 0 <= next_col < n or (next_row, next_col) in visited:
                dir_idx = (dir_idx + 1) % 4

            # 实际的下一个
            row += dirs[dir_idx][0]
            col += dirs[dir_idx][1]
        return res
```