54. Spiral Matrix

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

solution

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()

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