LC54　螺旋矩阵¶

中等通过率 55.6%python3核心代码模式矩阵样例通过牛客 AC数组矩阵模拟

牛客原题　源码

讲解章节：模拟

一句话

用上下左右四条边界围住未访问区域，每走完一条边就把那条边界往里收。

解题思路¶

这题考什么¶

螺旋遍历要解决的核心问题是「怎么知道该拐弯了」。一种写法是开一个同样大小的 visited 布尔矩阵，撞到边界或撞到访问过的格子就换方向，思路直白但要 O(m n) 额外空间。

更省的写法是维护四条边界 top / bottom / left / right，它们围出的矩形恰好是「还没输出过的部分」。每一圈按固定顺序走四条边，走完一条立刻把对应的边界往里收一格：

上边  从左到右走第 top 行，走完 top 加一
右边  从上到下走第 right 列，走完 right 减一
下边  从右到左走第 bottom 行，走完 bottom 减一
左边  从下到上走第 left 列，走完 left 加一

循环不变量是「[top, bottom] x [left, right] 这块矩形里的元素都还没被输出」。每条边走完并收缩后，不变量重新成立；当 top > bottom 或 left > right 时矩形已空，遍历结束。整个过程不需要方向数组，也不需要 visited，只用四个整数。这类边界模拟见模拟。

关键在于矩形退化成单行或单列时的重复输出。走完上边和右边之后，矩形可能已经空了；这时如果还照走下边和左边，就会把刚输出过的元素再吐一遍。所以第三条边前要重新确认 top <= bottom（还剩至少一行），第四条边前要重新确认 left <= right（还剩至少一列）。前两条边不用额外判断，因为循环入口的 top <= bottom and left <= right 刚刚保证过，而它们各自只把一条边界收了一格。

数据规模与复杂度¶

1 <= m, n <= 10，-100 <= matrix[i][j] <= 100。时间 O(m n)：每个格子恰好被输出一次。除输出数组外空间 O(1)。规模只有 10 x 10 = 100 个格子，怎么写都不会超时—— 这题考的是边界处理是否严谨，不是效率。

坑在哪¶

第三、四条边必须重新判边界，这是本题唯一真正的坑。实测 matrix = [[1,2,3]]（单行）：正确输出 [1,2,3]；去掉第三条边前的 top <= bottom 判断后输出 [1,2,3,2,1]，多吐了 2 和 1 这两个元素——上边走完 top 收成 1、bottom 还是 0，矩形已空，可下边那趟仍会从右往左把第 0 行重扫一遍。同理实测 matrix = [[1],[2],[3]]（单列）：正确输出 [1,2,3]；去掉第四条边前的 left <= right 判断后输出 [1,2,3,2]，多吐一个 2。注意两个判断各管各的反例：单行只有第三条边出问题，单列只有第四条边出问题，补一个漏一个仍然会错。
收边界的时机是走完一条边立刻收，不是四条边走完统一收。统一收的话，右边那趟的行范围还会包含已经输出过的 top 行，重复输出。
各条边的遍历区间要和已经收过的边界对齐：右边从 top 走到 bottom （此时 top 已经加过一，正好跳过左上角那个已输出的格子），下边从 right 走到 left（right 已经减过一），左边从 bottom 走到 top。 range 的倒序写法 range(right, left - 1, -1) 里终点写 left - 1 才能取到 left 本身，写成 left 会漏掉最左那一格。
循环条件里 top 与 left 的两个判断要用 and 连起来。只判其中一个，另一维度耗尽时会读到越界或重复的行列。
矩形是「未访问区域」而非「整个矩阵」，所以四条边界的初值分别是 0、m-1、0、n-1，而不是 1 和 m-2 之类的内缩值。
严格比对：螺旋顺序唯一确定，输出的元素个数必须恰好是 m * n，没有多解。

样例复核¶

matrix = [[1,2,3],[4,5,6],[7,8,9]]，期望 [1,2,3,6,9,8,7,4,5]。起始 top=0 bottom=2 left=0 right=2。

第一圈  上边 (0,0)(0,1)(0,2) -> 1 2 3，top 收成 1
        右边 行 1..2 的第 2 列 -> 6 9，right 收成 1
        top(1) <= bottom(2)，下边 第 2 行从列 1 到 0 -> 8 7，bottom 收成 1
        left(0) <= right(1)，左边 行 1 到 1 的第 0 列 -> 4，left 收成 1
第二圈  此时矩形只剩单格 (1,1)。上边 -> 5，top 收成 2
        右边 行 2..1 为空区间，right 收成 0
        top(2) <= bottom(1) 不成立，跳过下边
        left(1) <= right(0) 不成立，跳过左边
循环条件 top(2) <= bottom(1) 不成立，结束。

输出 1 2 3 6 9 8 7 4 5，与样例一致。第二圈那两次跳过正是坑 1 说的判断在起作用：少了它们，5 会被重复输出。

参考实现¶

solutions/leetcode/LC54/sol.py
from typing import List, Optional


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 四条边界围出的矩形 [top, bottom] x [left, right] 就是「还没输出过的区域」，
        # 这是全程的循环不变量。初值取整个矩阵的四角，不是内缩值
        top = 0
        bottom = len(matrix) - 1
        left = 0
        right = len(matrix[0]) - 1
        ans = []
        # 两个条件要用 and：任一维度耗尽，未访问矩形就空了
        while top <= bottom and left <= right:
            # 上边：第 top 行从左到右
            for c in range(left, right + 1):
                ans.append(matrix[top][c])
            # 走完立刻收，不能等四条边都走完再统一收——
            # 否则下面右边那趟的行范围还会包含刚输出过的 top 行
            top += 1
            # 右边：第 right 列自上而下。起点用收过之后的 top，正好跳过已输出的右上角
            for r in range(top, bottom + 1):
                ans.append(matrix[r][right])
            right -= 1
            # 第三条边必须重新确认还剩至少一行。实测 [[1,2,3]] 去掉这个判断会输出
            # [1,2,3,2,1]，把第 0 行从右往左重扫一遍，多吐 2 和 1 两个元素
            if top <= bottom:
                # 下边：第 bottom 行从右到左。终点写 left - 1 才能取到 left 本身
                for c in range(right, left - 1, -1):
                    ans.append(matrix[bottom][c])
                bottom -= 1
            # 第四条边必须重新确认还剩至少一列。实测 [[1],[2],[3]] 去掉这个判断会输出
            # [1,2,3,2]，多吐一个 2。它与上面那个判断各管各的反例，缺一不可
            if left <= right:
                # 左边：第 left 列自下而上。终点写 top - 1 才能取到 top 本身
                for r in range(bottom, top - 1, -1):
                    ans.append(matrix[r][left])
                left += 1
        return ans

LC54 螺旋矩阵¶