解析
54. Spiral Matrix
# - time: O(m*n)
# - space: O(m*n) -> O(1) extra space, and O(m*n) space for the output list
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
# current valid search range: col: [minCol, maxCol], row: [minRow, maxRow]
# this means that "while minRow <= maxRow and minCol <= maxCol"
minRow, maxRow = 0, len(matrix) - 1
minCol, maxCol = 0, len(matrix[0]) - 1
res = []
while minRow <= maxRow and minCol <= maxCol:
# get every element in the top row
for c in range(minCol, maxCol + 1):
res.append(matrix[minRow][c])
minRow += 1 # to exclude the min row
# get every element in the right col
for r in range(minRow, maxRow + 1):
res.append(matrix[r][maxCol])
maxCol -= 1
# [[1,2,3]] or [[1], [2], [3]]
# minCol > maxCol 说明没有任何 col 可以再被考虑了
# minRow > maxRow 说明没有任何 row 可以再被考虑了
# 所以如果满足任何条件,直接跳出
if minCol > maxCol or minRow > maxRow:
break
# get every element in the bottom row
for c in range(maxCol, minCol - 1, -1):
res.append(matrix[maxRow][c])
maxRow -= 1
# get every element in the left col
for r in range(maxRow, minRow - 1, -1):
res.append(matrix[r][minCol])
minCol += 1
return res
ref