Spiral Matrix
你会得到一个整数矩阵，它有 m 行和 n 列，以行列表的形式给出。按螺旋顺序返回矩阵中的所有值。
从左上角开始，沿着第一行向右移动，然后沿着最右侧一列向下移动，接着沿着最后一行向左移动，再沿着最左侧一列向上移动。继续顺时针向内一圈圈移动，直到每个值都恰好读取一次。
函数
- matrixinteger-2d-array
- 整数网格，表示为一个长度相同的行列表
- 返回值integer-array
- 从左上角开始，按顺时针螺旋顺序遍历矩阵中的每个值
约束条件
1 ≤ m, n ≤ 80，其中m = matrix.length，n = matrix[i].length- 每一行的长度都相同，为
n。 -100 ≤ matrix[i][j] ≤ 100
示例
- 输入
- matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
- 输出
- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
- 解释
- 数值沿着螺旋递增。外圈的数值从
1到10，内层是一列，只读一次：11, 12。
- 输入
- matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
- 输出
- [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
- 解释
- 外圈给出
7, 1, 5, 3, 6, -1, 4, 0, 8, 2。剩下的是一行9, -4，从左到右读取一次。
- 输入
- matrix = [[4], [1], [7]]
- 输出
- [4, 1, 7]
- 解释
- 单列中的值按从上到下的顺序读取。无法再向上读取，因为每个值都已经读取过了。
进阶
你能改为按逆时针顺序返回这些值吗？从左上角开始，先沿左侧一列向下。
提示
逐个打开提示，每个都会多透露一点。
看看完整绕一圈时读取的内容：顶行、右列、底行和左列。绕完一圈后，矩阵还剩下什么？
转完一圈后，剩下的是一个更小的矩阵，顶部和底部各少一行，两侧各少一列。保留四个边界：
top、bottom、left和right，每转完一圈就将它们向内移动。注意最后一层：它可能只有一行或一列。当
top ≤ bottom且left ≤ right时：从left到right读取顶行，然后从top+1到bottom读取右列。只有当top < bottom且left < right时，才从right-1向左回读底行，直到left，并从bottom-1向上读取左列，直到top+1。然后将四个边界都向内移动一步。
题解
问题在于如何记录访问情况。每个角都必须读取一次，而最内层可能只有一行或一列，此时走完整一圈会重复读取数值。你可以沿着路径前进，遇到阻挡时就右转；也可以用四个不断缩小的边界逐层剥去矩阵，无需额外内存。
前进，遇到障碍时向右转
思路
一个行走者从左上角的单元格出发，面朝右，并读取它所在的每个单元格。如果下一步会走出矩阵，或者走到已经读取过的单元格，它就向右转。边缘会挡住第一圈，而已读取的单元格会在之后的每一圈中充当墙壁，因此每一圈都在上一圈的范围内。
在第一个示例中，行走者沿着边缘读取 1 到 10。10 上方是已经读取过的 1，所以它转向 11，然后向下走到 12。让循环恰好运行 m × n 次，就不需要检测结束条件。时间复杂度为 O(m × n)，而 seen 网格会额外占用 O(m × n) 的内存。
算法
- 从第
0行、第0列开始，方向索引为d = 0，使用dr = [0, 1, 0, -1]、dc = [1, 0, -1, 0]，并将seen网格全部设为 false。 - 重复
m × n次：追加当前值，并将当前单元格标记为已访问。 - 如果下一个单元格超出矩阵范围或已访问，则使用
d = (d+1) % 4转向。 - 沿方向
d移动一步。
def spiralOrder(matrix):
rows, cols = len(matrix), len(matrix[0])
seen = [[False] * cols for _ in range(rows)]
# Directions in clockwise order: right, down, left, up.
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = c = d = 0
result = []
for _ in range(rows * cols):
result.append(matrix[r][c])
seen[r][c] = True
nr, nc = r + dr[d], c + dc[d]
# Blocked by the edge or by a cell already read: turn right.
if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
d = (d + 1) % 4
nr, nc = r + dr[d], c + dc[d]
r, c = nr, nc
return result用四个边界剥开各层
思路
用行 top 到 bottom、列 left 到 right 描述当前环。每一圈的每条边都从前一条边终点之后的一个单元格开始，因此每个角只会读取一次。然后将四个边界都向内移动。
只有一行或一列厚的环无法完整走完一圈。第二个示例中的最后一圈是行 9, -4：读取顶行时会读到两个值，如果再沿底行走回来，就会再次添加 9。在第三个示例中，沿单列向上走会再次读取 1。因此，只有当 top < bottom 且 left < right 时，才遍历底行和左列。
每个值都只读取一次，因此时间复杂度为 O(m × n)，额外内存只需四个整数。
算法
- 将
top = 0、bottom = m-1、left = 0、right = n-1设为初始值。 - 当
top ≤ bottom且left ≤ right时，从left到right读取顶行，并从top+1到bottom读取最右列。 - 如果
top < bottom且left < right，从right-1到left读取底行，并从bottom-1到top+1读取最左列。 - 将
top和left加 1，将bottom和right减 1。
def spiralOrder(matrix):
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
result = []
while top <= bottom and left <= right:
# Top row, left to right, then right column, top to bottom.
for c in range(left, right + 1):
result.append(matrix[top][c])
for r in range(top + 1, bottom + 1):
result.append(matrix[r][right])
# A layer one row or one column thick has no way back:
# walking back would read the same cells again.
if top < bottom and left < right:
# Bottom row, right to left, then left column, bottom to top.
for c in range(right - 1, left - 1, -1):
result.append(matrix[bottom][c])
for r in range(bottom - 1, top, -1):
result.append(matrix[r][left])
# Step in to the next layer.
top += 1
bottom -= 1
left += 1
right -= 1
return result
易错点和边界情况
- 跳过
top < bottom和left < right检查。这样，第二个示例最后会得到9, -4, 9，第三个示例会得到4, 1, 7, 1。 - 让每条边都从各自的第一个单元格遍历到各自的最后一个单元格。这样，每个角都会被读取两次。
- 在
top < bottom时循环。在3 × 3矩阵中，中心值永远不会被读取。 - 上下界都使用
matrix.length。这种写法适用于所有正方形输入，但不适用于3 × 4输入。 - 在 R 中，
3:2会得到3, 2，而不是空范围；请添加保护条件或使用seq_len。在 Lua 和 R 中，索引从 1 开始。
常见问题3
螺旋矩阵的时间复杂度和空间复杂度是多少？
时间复杂度是 O(m × n)，因为每个值只读取一次，而且答案包含所有值。使用四个边界逐层剥离只需 O(1) 的额外内存。遇到阻挡时转向的遍历需要一个 O(m × n) 的网格来记录已访问的单元格。
在螺旋遍历中，如何避免重复读取同一个值？
每条边都从上一条边结束位置后面的一个单元格开始，这样每个角都属于一条边。在只有一行或一列厚的层中，跳过底行和左列。
如何按螺旋顺序填充矩阵，而不是读取矩阵？
使用相同的四个边界和边，但改为写入而不是读取。经过每个单元格时，将从 1 开始的计数器值存入其中，每次加一。对于 n × n 矩阵，计数器最终会达到 n²。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def spiralOrder(matrix):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
预期输出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]