54. 螺旋矩阵

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if( matrix.empty() ){
            return ans;
        }
        int up=0;
        int down=matrix.size()-1;
        int left=0;
        int right=matrix[0].size()-1;
        while( true ){
            for( int i=left;i<=right;++i ){
                ans.push_back(matrix[up][i]);
            }
            if( ++up>down ){
                break;
            }
            for( int i=up;i<=down;++i ){
                ans.push_back(matrix[i][right]);
            }
            if( --right<left ){
                break;
            }
            for( int i=right;i>=left;--i ){
                ans.push_back(matrix[down][i]);
            }
            if( --down<up ){
                break;
            }
            for( int i=down;i>=up;--i ){
                ans.push_back(matrix[i][left]);
            }
            if( ++left>right){
                break;
            }
        }
        return ans;
    }
};

时间复杂度

$O(Mn)$

空间复杂度

$O(Mn)$

Java

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if( 0==matrix.length ){
            return ans;
        }
        int up=0;
        int down=matrix.length-1;
        int left=0;
        int right=matrix[0].length-1;
        while(true){
            for( int i=left;i<=right;i++){
                ans.add(matrix[up][i]);
            }
            if(++up>down){
                break;
            }
            for( int i=up;i<=down;i++){
                ans.add(matrix[i][right]);
            }
            if(--right<left){
                break;
            }
            for( int i=right;i>=left;i-- ){
                ans.add(matrix[down][i]);
            }
            if( --down<up ){
                break;
            }
            for( int i=down;i>=up;--i ){
                ans.add(matrix[i][left]);
            }
            if( ++left>right){
                break;
            }
        }


        return ans;
        
    }
}

时间复杂度

$O(Mn)$

空间复杂度

$O(Mn)$

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = [];
        if 0==len(matrix):
            return ans;
        up=0;
        down=len(matrix)-1;
        left=0;
        right=len(matrix[0])-1;
        while True:
            for i in range(left,right+1):
                ans.append(matrix[up][i]);
            up=up+1;
            if up>down:
                break;
            for i in range(up,down+1):
                ans.append(matrix[i][right]);
            right=right-1;
            if right<left:
                break;
            i=right;
            while i>=left:
                ans.append(matrix[down][i]);
                i=i-1;
            down=down-1;
            if down<up:
                break;
            i=down;
            while i>=up:
                ans.append(matrix[i][left]);
                i=i-1;
            left=left+1;
            if left>right:
                break;
        return ans;
        

时间复杂度

$O(Mn)$

空间复杂度

$O(Mn)$