描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]
则依次打印出数字
[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

解法一：魔方逆时针旋转法

模拟魔方逆时针旋转的方法，一直做取出第一行的操作即可
例如：
1 2 3
4 5 6
7 8 9
输出并删除第一行后，再进行一次逆时针旋转，就变成：
6 9
5 8
4 7
继续重复上述操作即可。

Java代码如下：

public ArrayList<Integer> printMatrix(int [][] matrix) {
        //只需要获取矩阵的第一行后将矩阵去除第一行再逆时针旋转一下就可以了
        ArrayList<Integer> res=new ArrayList<>();
        int count=0;
        while(true){
            if(count!=0){ //除了第一次读取矩阵以外都要旋转矩阵
                matrix=rotate(matrix);
            }
            for(int i=0;i<matrix[0].length;++i)
                res.add(matrix[0][i]);
            ++count;
            if(matrix.length==1) //当矩阵只剩下一行（已被列表添加完毕）时跳出循环
                break;
        }
        return res;
    }
    public int[][] rotate(int[][] mat){
        int row=mat.length;
        int col=mat[0].length;
        if(col==1){ //当输入的矩阵的列数只有一列时，直接转置返回即可
            int[][] res=new int[1][row-1];
            for(int i=1;i<row;++i){
                res[0][i-1]=mat[i][0];
            }
            return res;
        }
        int[][] res=new int[col][row-1]; //返回一个逆时针旋转90度的将原数组首行删去后新数组
        int res_i=0,res_j=0;
        for(int i=col-1;i>=0;--i){
            res_j=0;
            for(int j=1;j<row;++j){
                res[res_i][res_j++]=mat[j][i];
            }
            ++res_i;
        }
        return res;
    }

时间复杂度：最坏情况下为O(n^2),n为矩阵元素个数
空间复杂度：需要另一个数组去旋转矩阵，空间复杂度为O(n)，n为矩阵元素个数

解法二：纯暴力法

顺时针走法如下图：
图片说明

最直接的想法就是按照从左至右，从上至下，从右至左和从左至右四步遍历去做，走完一圈后行起始值加1，终止值减1，列起始值值加1，终止值减1。
最主要的问题是要考虑边界值，例如上图，4既在第一圈的上边也在第一圈的右边，即右上角，我们输出时，要求只从左至右时输出一个4即可，即1，2，3，4，同理还有右下角16，即8，12，16，左下角13，即15，14，13，左上角1，即9，5。
另外需根据行终止值和行起始值来判断是否需要遍历从右至左底行元素，需根据列终止值和列起始值来判断是否需要遍历从下至上左侧元素。

由上边想法直接上代码：

     public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> result = new ArrayList<>();
        int beginRow = 0;//起始行下标
        int maxRow = matrix.length-1;//最大行下标
        int beginColumn = 0;//起始列下标
        int maxColumn = matrix[0].length-1;//最大列下标
        while(maxRow >= beginRow && maxColumn >= beginColumn){
            //顶行 ==> 从左至右
            for(int i = beginColumn;i <= maxColumn;i++){
                result.add(matrix[beginRow][i]);
            }
            //最右侧列 ==> 从上至下 右上角元素已经添加，注意边界
            for(int i = beginRow+1;i <= maxRow;i++){
                result.add(matrix[i][maxColumn]);
            }
            //底行  ==> 从右至左 右下角的数字已经添加了，注意边界
            if(maxRow != beginRow){
                for(int i = maxColumn-1;i >= beginColumn;i--){
                    result.add(matrix[maxRow][i]);
                }
            }

            //最左侧列 ==> 从下至上 左下角的数字已经添加了，注意边界
            if(maxColumn != beginColumn){
                for(int i= maxRow-1;i > beginRow;i--){
                    result.add(matrix[i][beginColumn]);
                    }
            }

        beginRow++;
        maxRow--;
        beginColumn++;
        maxColumn--;
        }
        return result;
    }

时间复杂度为：O(n),n为矩阵中元素个数
空间复杂度为：O(1)