54: Spiral Matrix 螺旋矩阵

给你一个 m 行 n 列的矩阵（m × n），请按顺时针螺旋顺序，返回矩阵中的所有元素。这道题在 LeetCode 上属于中等难度，但思路其实挺直观的，关键是怎么把“绕圈”的过程转换成代码逻辑。

题目描述很简单：

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

先看两个例子：

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
 [1, 2, 3, 4],
 [5, 6, 7, 8],
 [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路：

参考例二，观察一下索引的改变方式：(0,0) → (0,3) → (2,3) → (2,0) → (1,0) → (1,2)。

从 (0,3) 看，分别是：向下时横坐标自增1，到2；向左时纵坐标自减1，到0；向上时横坐标自减1，到1；向右时纵坐标自增1，到2。

假如是一个 m×n 的矩阵，从 (0, m-1) 开始，向下移动 n-1 次到达最下面，然后向左移动 m-1 次，再向上移动 n-2 次，接着向右移动 m-2 次……之后就是：向下 n-3，向左 m-3，向上 n-4，向右 m-4。每次转向，m 或 n 都会自减1。

这个思路的核心在于：每次走完一条边，对应的边界就向内收索一格。网上的很多解法直接操作索引坐标，每次都要重新计算参考点，其实本质和这个思路差不多，但个人觉得用“边界收索”的方式更容易理解。

Ja va 实现：

class Solution {
    public List spiralOrder(int[][] matrix) {
        List nums = new ArrayList();
        if (matrix.length == 0 || matrix[0].length == 0) return nums;
        int row = matrix.length - 1, col = matrix[0].length - 1, m = 0, n = 0, i = -1, tmp = 0;
        while (row >= 0 && col >= 0) {
            switch (i % 4) {
                case 0: // 向下
                    for (tmp = 0; tmp < row; tmp++) nums.add(matrix[++m][n]);
                    row -= 1;
                    break;
                case 1: // 向左
                    for (tmp = 0; tmp < col; tmp++) nums.add(matrix[m][--n]);
                    col -= 1;
                    break;
                case 2: // 向上
                    for (tmp = 0; tmp < row; tmp++) nums.add(matrix[--m][n]);
                    row -= 1;
                    break;
                case 3: // 向右
                    for (tmp = 0; tmp < col; tmp++) nums.add(matrix[m][++n]);
                    col -= 1;
                    break;
                default: // 初始方向（向右，先走完第一行）
                    for (tmp = 0; tmp <= col; tmp++) nums.add(matrix[m][n++]);
                    tmp = 0;
                    n -= 1;
                    break;
            }
            i++;
        }
        return nums;
    }
}

注意点：

先判断是否为空数组，判断条件的顺序不能颠倒。因为如果 matrix.length == 0 判断为 true，后面的 matrix[0].length == 0 就不会再执行，直接返回空数组。但如果把 matrix[0].length == 0 放在前面，当输入数组为空时，matrix[0] 会报错——因为 matrix 根本没有 0 号索引。这一点在老手看来是常识，但新手容易踩坑。

Python3 实现：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return []
        nums = []
        m = 0
        n = 0
        row = len(matrix) - 1
        col = len(matrix[0]) - 1
        flag = 0
        # 先走完第一行
        for n in range(col + 1):
            nums.append(matrix[m][n])
        while row >= 0 and col >= 0:
            if flag % 4 == 0:      # 向下
                for i in range(row):
                    m += 1
                    nums.append(matrix[m][n])
                row -= 1
            elif flag % 4 == 1:    # 向左
                for i in range(col):
                    n -= 1
                    nums.append(matrix[m][n])
                col -= 1
            elif flag % 4 == 2:    # 向上
                for i in range(row):
                    m -= 1
                    nums.append(matrix[m][n])
                row -= 1
            elif flag % 4 == 3:    # 向右
                for i in range(col):
                    n += 1
                    nums.append(matrix[m][n])
                col -= 1
            flag += 1
        return nums

注意点：

Python 没有 switch...case... 语句，所以这里用 if-elif 来实现。另外，Python 的 for 循环可操作性很强，可以直接操作索引坐标来改变遍历方式，这里不再赘述。