NC38 螺旋矩阵

给出一个 n n n 行 m m m 列的二维数组，按螺旋的顺序返回矩阵中的所有元素。

比如，输入为：

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

输出为：

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

观察上图，螺旋遍历可定义为从左上角开始，按照顺时针方向，从外向内依次遍历所有元素。

如上图示，可将二维数组拆解为若干个环。由外向内的，从左上角开始遍历每一个环，即可完成对整个二维数组的螺旋遍历。特殊的，当行或列为奇数时，位于中心处的“环”只有一行或一列。

接下来，将整个问题拆解为三个步骤：

• 确定环的数量
• 确定每个环包含的元素
• 由外向内遍历每一个环

观察上图，环的数量取决于 n n n 和 m m m 中较小值，不妨设 x = min ⁡ ( n , m ) x=\min(n,m) x=min(n,m)，尝试寻找 x x x 和环数 c n t cnt cnt 之间的规律：

• x = 1 x = 1 x=1 ， c n t = 1 cnt=1 cnt=1
• x = 2 x = 2 x=2 ， c n t = 1 cnt=1 cnt=1
• x = 3 x = 3 x=3 ， c n t = 2 cnt=2 cnt=2
• x = 4 x = 4 x=4 ， c n t = 2 cnt=2 cnt=2
• …

不难总结出规律 c n t = ⌈ x 2 ⌉ cnt = \lceil\frac{x}{2}\rceil cnt=⌈2x​⌉。

总结：一个 n n n 行 m m m 列的二维数组，令 x = min ⁡ ( n , m ) x = \min (n,m) x=min(n,m)，则二维数组可拆解为 ⌈ x 2 ⌉ \lceil\frac{x}{2}\rceil ⌈2x​⌉ 个环。由外向内，第 i i i 个环的起始位置 ( i , i ) (i,i) (i,i)， i ∈ [ 0 , ⌈ x 2 ⌉ ) i ∈ [0,\lceil\frac{x}{2}\rceil) i∈[0,⌈2x​⌉)。

继续观察，第 i i i 环可以拆解为四部分：

• 第一部分：第 i i i 行中，第 i i i 列到第 m − i − 1 m-i-1 m−i−1 列。
• 第二部分：第 m − i − 1 m-i-1 m−i−1 列中，第 i + 1 i+1 i+1 行到 n − i − 2 n-i-2 n−i−2 行。
• 第三部分：第 n − i − 1 n-i-1 n−i−1 行中，第 m − i − 1 m-i-1 m−i−1 列到第 i i i 列。
• 第四部分：第 i i i 列中，第 n − i − 2 n-i-2 n−i−2 行到第 i + 1 i+1 i+1 行。

需要注意，两部分之间的元素可能有重合：

• 当 i = n − i − 1 i = n-i-1 i=n−i−1 时，第一部分和第三部分的元素是一致的。
• 当 i = m − i − 1 i = m-i-1 i=m−i−1 时，第二部分和第四部分的元素是一致的。

在遍历环时，要注意处理重复的情况。把上述问题想清楚后，不难写出下述代码：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> anw;
        int n = matrix.size();
        if (n == 0) {
            return anw;
        }
        int m = matrix[0].size();
        int cnt = (min(n,m)+1)/2;
        anw.reserve(n*m);
        for (int i = 0; i < cnt; i++) {
            for (int j = i; j <= m-i-1; j++) {
                anw.emplace_back(matrix[i][j]);
            }
            for (int j = i+1; j <= n-i-2; j++) {
                anw.emplace_back(matrix[j][m-i-1]);
            }
            if (n-i-1 != i) {
                for (int j = m-i-1; j >= i; j--) {
                    anw.emplace_back(matrix[n-i-1][j]);
                }
            }
            if (i != m-i-1) {
                for (int j = n-i-2; j >= i+1; j--) {
                    anw.emplace_back(matrix[j][i]);
                }
            }
        }
        return anw;
    }
};