面试题29. 顺时针打印矩阵

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

示例 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**思路一：**确定上下左右四个边界，遍历方向为从左到右、从上到下、从右到左、从下到上，从左到右移动完后上边界下移(如果上边界移到了下边界之下，说明遍历完了)，从上到下移动完后右边界左移(如果右边界移动到左边界之左，说明遍历完了)，剩下两个方向同理。

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length ==0) {
            return new int [0];
        }
        int [] res = new int [matrix.length * matrix[0].length];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, index = 0;
        while(true) {
            for(int i = l; i <= r; i++) res[index++] = matrix[t][i];
            if(++t > b) break;
            for(int i = t;i <= b; i++) res[index++] = matrix[i][r];
            if(--r < l) break;
            for(int i = r; i >= l; i--) res[index++] = matrix[b][i];
            if(--b < t) break;
            for(int i = b; i >= t; i--) res[index++] = matrix[i][l];
            if(++l > r) break;
        }
        return res;
    }
}

思路二(时空复杂度过高，不推荐)：用一个数组来标记是否到达过某个位置，不断的遍历四个方向，直到某一次朝哪个方向都没走动，说明遍历完了。

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0){
            return new int [0];
        }
        int row = matrix.length;
        int col = matrix[0].length;
        //false代表没走过
        boolean [] [] map = new boolean [row] [col] ;
        int [] [] dir = new int [] []{{0,1},{1,0},{0,-1},{-1,0}};
        int [] res = new int [row * col]; 
        res[0] = matrix[0][0];
        map[0][0] = true;
        int x = 0;
        int y = 0;
        int idx = 1;
        while(true){
            boolean flag = false;
            for(int i = 0;i < dir.length;i++){
                int tempx = x + dir[i][0];
                int tempy = y + dir[i][1];
                while(tempx >=0 && tempx < row && tempy >= 0 && tempy < col && !map[tempx][tempy]){
                    flag = true;
                    map[x][y] = true;
                    x = tempx;
                    y = tempy;
                    res[idx++] = matrix[x][y];
                    tempx = x + dir[i][0];
                    tempy = y + dir[i][1];
                }
                if(i < dir.length - 1){
                    tempx = x + dir[i + 1][0];
                    tempy = y + dir[i+1][1];
                }
            }
            if(!flag){
                break;
            }
        }
        return res;
    }
}