题解 | #顺时针打印矩阵#

可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。

对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于(bottom,right)，按照如下顺序遍历当前层的元素。
1、从左到右遍历上侧元素，依次为(top,left) 到(top,right)。
2、从上到下遍历右侧元素，依次为(top+1,right) 到 (bottom,right)。
3、如果 left<right 且top<bottom，则从右到左遍历下侧元素，依次为(bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为(bottom,left) 到(top+1,left)。
遍历完当前层的元素之后，将left 和top 分别增加 1，将 right 和 bottom 分别减少 11，进入下一层继续遍历，直到遍历完所有元素为止。

图解：从左向右、从上向下、从右向左、从下向上

Python版本

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        if not matrix:
            return matrix
        # 返回列表
        result = []
        shang = 0
        xia = len(matrix)-1
        left = 0
        right = len(matrix[0])-1
        
        while True:
            # 左到右
            for i in range(left, right+1):
                # 存储遍历结果
                result.append(matrix[shang][i])
            shang += 1
            if shang > xia:
                break
            # 上到下
            for i in range(shang, xia+1):
                result.append(matrix[i][right])
            right -= 1
            if left > right:
                break
            # 右到左
            for i in range(right, left-1, -1):
                result.append(matrix[xia][i])
            xia -= 1
            if shang > xia:
                break
            # 下到上
            for i in range(xia, shang-1, -1):
                result.append(matrix[i][left])
            left += 1
            if left > right:
                break
        return result

复杂度分析：

时间复杂度O(MN)：其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度O(1)：除了输出数组以外，空间复杂度是常数。

算法思想二：递归

递归的思想和非递归的思想相差不大，递归是首先打印最外层的元素，将内层的矩阵作为一个全新的矩阵进行递归。

对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于(bottom,right)，按照如下顺序遍历当前层的元素。
1、从左到右遍历上侧元素，依次为(top,left) 到(top,right)。
2、从上到下遍历右侧元素，依次为(top+1,right) 到 (bottom,right)。
3、如果 left<right 且top<bottom，则从右到左遍历下侧元素，依次为(bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为(bottom,left) 到(top+1,left)。
遍历完当前层的元素之后，将left 和top 分别增加 1，将 right 和 bottom 分别减少 11，进入下一次递归，直到遍历完所有元素为止。

图解：首先递归最外层，再递归第二层。。。。

JAVA版本

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        if(matrix==null||matrix.length==0) return res;
        int m = matrix.length;
        int n = matrix[0].length;
        
        print(0, n-1, 0, m-1, matrix);
        return res;
    }
    public void print(int left, int right, int top, int bottom, int [][] matrix){
        // 从左到右
        for(int i = left; i <= right; i ++) res.add(matrix[top][i]);
        // 下一层
        top ++;
        if(left > right || top > bottom) return;
        // 从上到下
        for(int i = top; i <= bottom; i ++) res.add(matrix[i][right]);
        right --;
        if(left > right || top > bottom) return;
        // 从右到左
        for(int i = right; i >= left; i --) res.add(matrix[bottom][i]);
        bottom --;
        if(left > right || top > bottom) return;
        // 从下到上
        for(int i = bottom; i >= top; i --) res.add(matrix[i][left]);
        left ++;
        // 递归
        print(left, right, top, bottom, matrix);
    }
}