54.螺旋矩阵

难度：中等

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 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]

提示：

• m = matrix.length
• n = matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

解题思路

联想 59 题，采用同样的方法，定义当前左右上下边界 left、right、top、bottom，直接模拟遍历过程即可。

差别的地方在于，这题里的矩阵不一定为正方形，可以为长方形，那么在填充 result 的过程中，会存在类似 top <= bottom 已经不满足，但 left <= right 仍然满足的情况，如果不加以控制，那么 result 末尾的地方，可能会填充进一些多余的值进去。

这里我采用了 subList() 来截断 result 里多余的内容，保证了结果的正确性。

也可以在内层循环外多加一些局部判断来达到避免填充多余元素的效果，或者在每个内层循环条件里加上 && start <= m * n，效果一样。

我的代码

public List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int left = 0, right = n - 1, top = 0, bottom = m - 1;
    List<Integer> result = new ArrayList<>();
    int num = 1;
    while (num <= m * n) {
        for (int i = left; i <= right; i++) {// 从左到右
            result.add(matrix[top][i]);
            num++;
        }
        top++;
        for (int i = top; i <= bottom; i++) {// 从上到下
            result.add(matrix[i][right]);
            num++;
        }
        right--;
        for (int i = right; i >= left; i--) {// 从右到左
            result.add(matrix[bottom][i]);
            num++;
        }
        bottom--;
        for (int i = bottom; i >= top; i--) {// 从下到上
            result.add(matrix[i][left]);
            num++;
        }
        left++;
    }
    return result.subList(0, m * n);
}

时间复杂度：O(m * n)

空间复杂度：O(m * n)

总结

充分理解题意，然后模仿遍历的过程。