1.螺旋矩阵https://leetcode-cn.com/problems/spiral-matrix/
看到这题我第一时间想到的也是用辅助矩阵visited，时间复杂度和空间复杂度都是O(mn)
1 class Solution: 2 def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 3 if not matrix or not matrix[0]: 4 return list() 5 6 rows, columns = len(matrix), len(matrix[0]) 7 visited = [[False] * columns for _ in range(rows)] 8 total = rows * columns 9 order = [0] * total 10 11 directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] 12 row, column = 0, 0 13 directionIndex = 0 14 for i in range(total): 15 order[i] = matrix[row][column] 16 visited[row][column] = True 17 nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1] 18 if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]): 19 directionIndex = (directionIndex + 1) % 4 20 row += directions[directionIndex][0] 21 column += directions[directionIndex][1] 22 return order
看到官方还有一个按层来模拟的方法，巧妙地省去了辅助数组，节省了空间。这里有一个疑问，答案说除了输出数组以外，空间复杂度是常数，那输出数组不算吗？
1 class Solution: 2 def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 3 if not matrix or not matrix[0]: 4 return list() 5 6 rows, columns = len(matrix), len(matrix[0]) 7 order = list() 8 left, right, top, bottom = 0, columns - 1, 0, rows - 1 9 while left <= right and top <= bottom: 10 for column in range(left, right + 1): 11 order.append(matrix[top][column]) 12 for row in range(top + 1, bottom + 1): 13 order.append(matrix[row][right]) 14 if left < right and top < bottom: 15 for column in range(right - 1, left, -1): 16 order.append(matrix[bottom][column]) 17 for row in range(bottom, top, -1): 18 order.append(matrix[row][left]) 19 left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1 20 return order