题目描述

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

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

题解

方法一：模拟、设定边界

解题思路

根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5]可以发现，顺时针打印矩阵的顺序是“从左向右，从上到下，从右向左，从下向上”循环。

• 因此，考虑设定矩阵的“左，上，右，下”四个便捷，模拟以上矩阵遍历顺序。

算法流程：

1. 空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。

2. 初始化： 矩阵 左、右、上、下 四个边界 l，r，t，b，用于打印的结果列表 res。

3. 循环打印： “从左向右，从上向下，从右向左，从下向上”四个方向循环，每个方向打印中做以下三件事（各方向的具体信息见下表）：

   1. 根据边界打印，即将元素按顺序添加至列表 res 尾部；
   2. 边界向内收缩 1（代表已被打印）；
   3. 判断是否打印完毕（边界是否相遇），若打印完毕则跳出。

4. 返回值： 返回 res 即可。

复杂度分析：

时间复杂度 O(MN) ： M, N 分别为矩阵行数和列数。
空间复杂度 O(1)： 四个边界 l，r，t，b 使用常数大小的 额外 空间（res 为必须使用的空间）。

代码

Java 代码利用了 ++ 操作的便利性

• res[x++] 等价于先给 res[x] 赋值，再给 x 自增 1；
• ++t > b 等价于先给 t 自增 1，再判断 t > b 逻辑表达式。

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

个人理解

1. 规律： 该解法有一个规律，就是顺时针打印对应的是一个循环，这个循环就是从左到右，从上到下，从右到左，从下到上，通过该循环可以解决方向的问题，我们不必再控制方向如何变，我们只需要一个 while 循环，在条件满足的情况下，依次执行上述各个方向遍历，就是方向的控制。
2. 边界设置： left=0，right=matrix[0].length，top=0，bottom=matrix.length。
3. 需要定义一个返回结果数组 result[]，同时还需要定义一个索引下标，用来向数组中写数据使用，即 index=0。
4. 循环赋值： 我们应该怎样循环赋值呢，以从左向右为例，我们需要找到左边界和右边界，即 left和 right，从左向右依次遍历即可，那么我们怎么确定是数组中的哪个值呢？我们还需要知道我们位于哪一行，这时候就需要 top 参数了，通过 matrix[top][i] 我们就可以知道这是数据中的哪个值了。
5. 判断什么边界： 当我们按照一个方向循环遍历完事之后，我们应该如何判断边界，判断什么边界呢？以从左向右 为例，该方向遍历完成之后，我们下一个方向应该是从上到下，所以我们应该判断从上到下的边界是否超过。
6. 如何比较边界： 以从左向右为例，我们应该比较上下边界了，那么怎样才算超出边界呢，top=bottom ？当 top=bottom 时说明此时应该为最后遍历的一行，所以应该 top>bottom的时候超出边界了。
7. 二维数组下标： 在这个过程中一定不弄反了坐标，top，bottom 是 横坐标，left，right 是 纵坐标。

以下代码是按照自我理解写的，简化后就是上述代码：

class Solution {
    public int[] spiralOrder(int[][] matrix) {

        if (matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1;
        int length = matrix.length*matrix[0].length;
        int[] result = new int[length];
        int index = 0;

        while (true) {
            //从左向右
            for (int i=left; i<=right; i++) {
                result[index] = matrix[top][i];
                index++;
            }
            top++;
            if (top > bottom) {
                break;
            }
            //从上到下
            for (int i=top; i<=bottom; i++) {
                result[index] = matrix[i][right];
                index++;
            }
            right--;
            if(left > right) {
                break;
            }
            //从右到左
            for (int i=right; i>=left; i--) {
                result[index] = matrix[bottom][i];
                index++;
            }
            bottom--;
            if(top > bottom) {
                break;
            }
            //从下到上
            for( int i=bottom; i>=top; i--) {
                result[index] = matrix[i][left];
                index++;
            }
            left++;
            if (left > right) {
                break;
            }

        }

        return result;
    }
}

来源

作者：jyd
链接：leetcode-cn.com/problems/shun-shi-...
来源：力扣（LeetCode）

本作品采用《CC 协议》，转载必须注明作者和本文链接