54. Spiral Matrix.md

54. Spiral Matrix

思路

题目要求顺时针螺旋遍历一个二维数组。

思路一

根据题意，直接模拟。以遍历一圈为一个循环周期，其中一圈为分为向右、下、左、上遍历。假设二维数组有m行，n列，那么一共有多少圈呢？

• 如果只看水平方向（向右和向左），因为遍历一圈（最多）需要消耗两行，则需要遍历(m + 1) / 2圈；
• 同理，如果只看垂直方向，则需要遍历(n + 1) / 2圈；

综合以上两个因素可知一共需要遍历min((m + 1) / 2, (n + 1) / 2)圈。

循环圈数知道了，那么如何构造每一圈的四个方向呢？假设当前圈的遍历起点为(i，i)（行列坐标一定是相等的，想想为什么）:

• 向右: 行坐标始终是i,而列坐标从i到n - i - 1(含，下同)；
• 向下: 列坐标始终是n - i - 1，而行坐标从i + 1到m - i - 1；
• 向左: 行坐标始终是m - 1 - i，而列坐标从n - 2 - i到i，需要注意的是，此时的行坐标应该大于向右时的行坐标即m - 1 - i > i，否则这一行在向右遍历时已经遍历过了，就不需要再遍历了。
• 向上: 列坐标始终是i，行坐标从m - 2 - i到i + 1，与向左时类似，此时需要满足列坐标小于向下时的列坐标，即i < n - i - 1。

若n为所有元素个数，则时间复杂度O(n)，空间复杂度为O(1)

思路二

思路一就已经很快了，但是需要十分注意一些边界条件，容易出错，而且若想推广到逆时针需要改动很大。下面介绍另外一种好理解且很方便推广到逆时针的方法，来源于讨论区。

先来看看这样一个例子:

1   2  3  4  5
6   7  8  9 10
11 12 13 14 15

还是像思路一一样分成四个方向：向右、向下、向左、向上。那么下面这个例子的遍历过程如下(假设起始行列坐标为(0，-1)):

• 向右5次；
• 向下2次；
• 向左4次；
• 向上1次；
• 向右3次；
• 向下0次，结束。

如果我们将向右和向左都看成一个方向（水平），那么此方向移动的次数就是5->4->3；将向下和向上都看做是一个方向（竖直），则移动次数就是2->1->0，所以我们可以发现规律就是水平和竖直两个方向交替移动，每个方向每次的移动步数都是各自递减1的。而水平初始移动次数是n，竖直初始移动次数是m-1，则遍历过程就是:

1. 水平（向右）移动n次；
2. 竖直（向下）移动m-1次；
3. 水平（向左）移动n-1次；
4. 竖直（向上）移动m-2次；
5. ......

直到移动次数变为0即遍历完成。所以该过程有两个周期，一个是水平与竖直的周期，周期为2；另一个就是具体方向的周期，周期为4。我们可以用一个大小为2的初始值为[n, m-1]的数组steps记录还剩下的两个方向的步数。为了方便四个方向的移动运算，我们可以定义一个二维的const数组dirs，其值为[[0, 1], [1, 0], [0, -1], [-1, 0]]。

此方法可以很方便地推广到逆时针螺旋遍历，只需要把方向（右、下、左、上）改成（下、右、上、左）即可，即改动一下dirs的元素排列顺序即可。

复杂度同思路一。

C++

思路一

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int>res;
        if(matrix.empty()) return res;
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < min((m + 1) / 2, (n + 1) / 2); i++){
            for(int j = i; j <= n - i - 1; j++) // 向右
                res.push_back(matrix[i][j]);
            
            for(int j = i + 1; j <= m - 1 - i; j++) // 向下
                res.push_back(matrix[j][n - 1 - i]);
            
            if(m - 1 - i > i) // 为了避免和向右重复
                for(int j = n - 2 - i; j >= i; j--) // 向左
                    res.push_back(matrix[m - 1 - i][j]);

            if(i < n - 1 - i) // 为了避免和向下重复
                for(int j = m - 2 - i; j >= i + 1; j--) // 向上
                    res.push_back(matrix[j][i]);
        }
        return res;
    }
};

思路二

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int>res;
        if(matrix.empty()) return res;
        int m = matrix.size(), n = matrix[0].size();
        const vector<vector<int>>dirs{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // 右、下、左、上
        vector<int>steps{n, m-1}; 
    
        int iDir = 0;   // 方向的下标
        int ir = 0, ic = -1;    // 初始行列坐标
        while(steps[iDir % 2]){  // 当前是水平or竖直，周期为2
            for(int i = 0; i < steps[iDir % 2]; i++){  // 在当前方向移动steps[iDir % 2]次
                ir += dirs[iDir][0]; ic += dirs[iDir][1];
                res.push_back(matrix[ir][ic]);
            }
            steps[iDir % 2]--;
            iDir = (iDir + 1) % 4; // 下一次的方向，周期为4
        }
        return res;
    }
};