题目链接：Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

[ 
 [ 1, 2, 3 ], 
 [ 4, 5, 6 ], 
 [ 7, 8, 9 ] 
]

You should return [1,2,3,6,9,8,7,4,5].

这道题的要求是给定m*n的矩阵，按螺旋顺序返回所有元素（顺时针）。

简单的数组操作问题，只需要按右、下、左、上的顺序逐行或列遍历数组。不过需要注意边界问题，假设当前在[x, y]位置：

  • 向右遍历时，由于x不变，y每次加1，因此要求y要小于n-x即可;
  • 向下遍历时，由于y不变，x每次加1，因此要求x要小于m-(n-y-1)即可;
  • 向左遍历时，由于x不变，y每次减1，因此要求y要不小于m-x-1即可;
  • 向上遍历时，由于y不变，x每次减1，因此要求x要不小于y+1即可。

时间复杂度：O(mn)

空间复杂度：O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution
{
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix)
    {
        vector<int> vi;
        
        if(matrix.size() == 0)
            return vi;
        
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = 0, mn = m * n - 1;
        vi.push_back(matrix[x][y]);
        
        while(mn > 0)
        {
            while(y + 1 < n - x && mn -- > 0)
                vi.push_back(matrix[x][++ y]);
            
            while(x + 1 < m - (n - y - 1) && mn -- > 0)
                vi.push_back(matrix[++ x][y]);
            
            while(y - 1 >= m - x - 1 && mn -- > 0)
                vi.push_back(matrix[x][-- y]);
            
            while(x - 1 >= y + 1 && mn -- > 0)
                vi.push_back(matrix[-- x][y]);
        }
        
        return vi;
    }
};