顺时针打印矩阵（3种思路4个写法）

问题简述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

详细描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：
    输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]
示例 2：
    输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：
    0 <= matrix.length <= 100
    0 <= matrix[i].length <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：螺旋遍历

• 循环遍历 4 个方向的路线，中间做好边界判断（虽然思路简单，但是写起来很容易出错）；

Python：写法1（更朴素）

class Solution:
    def spiralOrder(self, matrix: [[int]]) -> [int]:
        """"""        
        ret = []
        if not matrix or not matrix[0]:
            return ret

        m, n = len(matrix), len(matrix[0])  # m行n列
        # 设置左、右、上、下边界
        l, r, t, b, = 0, n - 1, 0, m - 1

        while True:
            # 依次遍历 4 个方向
            # 因为最后一趟遍历哪个方向都有可能，所以需要 4 个 break

            # left to right, top+=1
            for i in range(l, r + 1):
                ret.append(matrix[t][i])
            t += 1
            if t > b:
                break

            # top to bottom, right-=1
            for i in range(t, b + 1):
                ret.append(matrix[i][r])
            r -= 1
            if l > r:
                break

            # right to left, bottom-=1
            for i in range(r, l - 1, -1):  # 逆序
                ret.append(matrix[b][i])
            b -= 1
            if t > b:
                break

            # bottom to top, left+=1
            for i in range(b, t - 1, -1):  # 逆序
                ret.append(matrix[i][l])
            l += 1
            if l > r:
                break

        return ret

• 写法 1 的逻辑足够清晰，但不够通用（优雅），比如要遍历 8 个方向时；

• 另一种写法会预先定义各方向的 step，详见代码；

Python：写法2（更优雅）

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        # 4 个方向的 step
        steps = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        m, n = len(matrix), len(matrix[0])

        # 法1）使用一个 set 或矩阵记录已经访问过的位置
        # visited = set()
        # visited = [[False] * n for _ in range(m)]  # m行n列
        # 法2）直接在 matrix 上修改访问过的位置
        visited = 10001

        ret = []
        i, j = 0, 0  # 记录当前访问的位置
        k = 0  # 已经访问过的位置数量
        d = 0  # 方向标记
        while k < m * n:
            ret.append(matrix[i][j])
            matrix[i][j] = visited
            # visited.add((i, j))
            # visited[i][j] = True
            k += 1

            # 下一个位置
            nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
            # 判断下一个位置是否合法，或是否访问过
            if not 0 <= nxt_i < m or not 0 <= nxt_j < n or matrix[nxt_i][nxt_j] == visited:
                # 如果不合法或已经访问过，进入下一个方向
                d = (d + 1) % 4
                nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
            i, j = nxt_i, nxt_j

        return ret

思路2：层层递归

• 每次遍历完最外圈后，递归遍历下一圈；

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """"""
        def dfs(M):
            # 注意：这里除了要判断 M，还要判断 M[0]，因为之后代码中的切片操作可能会使行数据为空列表 []
            if not M or not M[0]: return []

            m, n = len(M), len(M[0])

            # 如果最内圈是一行或一列，那么该行/列的遍历方向一定是 左→右 或 上→下
            if m == 1:
                return M[0]
            if n == 1:
                return [row[0] for row in M]

            # 最外一圈的数据
            ret = M[0] \
                + [row[-1] for row in M[1:]] \
                + M[-1][-2::-1] \
                + [row[0] for row in M[-2:0:-1]]

            return ret + dfs([row[1:-1] for row in M[1:-1]])

        return dfs(matrix)

思路3：“削苹果”

• 每次“削去”矩阵的第一层，然后将矩阵逆时针旋转 90 度，循环削去第一层；

• 而逆时针旋转的操作在 python 中可以用一行代码完成！

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ret = []
        while matrix:
            ret += list(matrix.pop(0))  # zip 后的结果是一个元组，这里转成 list，不过实际上不转换也可以；

            # 核心操作，逆时针旋转 90 度
            matrix = list(zip(*matrix))[::-1]
        
        return ret

# 图解 `list(zip(*matrix))[::-1]` 这一步做了什么：

# 假设已经 pop 了第一行，此时矩阵剩余的部分是：
[4 5 6]  # 记为 l1
[7 8 9]  # 记为 l2，如果有 n 行，则记为 ln

# zip(*matrix) 包含了两个知识点：一个是 zip() 函数，一个是 * 号的作用；
# zip(*matrix) 实际上等价于 zip(l1, l2, ..., ln)
# 经过这一步 matrix 将转化为（相当于做了一次转置）
[4 7]
[5 8]
[6 9]

# 这时再将 matrix 做一次逆序，就得到了逆时针旋转 90 度的结果
[6 9]
[5 8]
[4 7]