矩阵#中等#螺旋矩阵

前文

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

示例 1：

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

示例 2：

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

正文

要点：

• 怎么表示这种顺时针的路径
• 观察很好理解，顺时针即可，让代码理解顺时针
• 顺序是处理第一行 最后一列 最后一行 第一列，然后剩下的矩阵重复这个操作直至没有剩下的矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

    }
};

解法1

通过示例找规律， 示例解释1：

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

以行列位置来说，设起始点是第一行第一个元素为[1][1]，则依次为

开始行不动，列增加直到列边界

[1][1], [1][2], [1][3]

此时列到达边界继续且列不动行增加

[2][3], [3][3]

此时行达到边界继续且行不动列减少

[3][2], [3][1]

此时列到达边界继续且列不动行减少

[2][1] 注意，这里接下来应该是[1][1]，但边界应该是动态改变的，此时应该是行不变，列增加

[2][2]

按照这个规律，可以编写从起始点开始的以螺旋形式遍历矩阵的代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        vector<int> res;
        int row_begin = 0, row_end = matrix.size() - 1;
        int col_begin = 0, col_end = matrix[0].size() - 1;

        int x = 0, y = -1;


        while(1) {
            // cout << x << ", " << y << endl;
            // res.push_back(matrix[x][y]);
            // 按照顺序规律进行循环
            while(y != col_end) {
                ++y;
                res.push_back(matrix[x][y]);
            }
            ++row_begin;
            while(x != row_end) {
                ++x;
                res.push_back(matrix[x][y]);
            }
            --col_end;
            if (row_begin > row_end) return res;
            if (col_end < col_begin) return res;
            while(y != col_begin) {
                --y;
                res.push_back(matrix[x][y]);
            }
            ++col_begin;
            while(x != row_begin) {
                --x;
                res.push_back(matrix[x][y]);
            }
            --row_end;
            if (col_begin > col_end) return res;
            if (row_end < row_begin) return res;
            // if (y == col_end) {
            //     ++x;
            //     ++row_begin;
            //     if (row_begin > row_end) return res;
            //     continue;
            // } else {
            //     ++y;
            //     continue;
            // }
            // if (x == row_end) {
            //     --y;
            //     --col_end;
            //     if (col_end < col_begin) return res;
            //     continue;
            // } else {
            //     ++x;
            //     continue;
            // }
            // if (y == col_begin) {
            //     --x;
            //     --row_end;
            //     if (row_end < row_begin) return res;
            //     continue;
            // } else {
            //     --y;
            //     continue;
            // }
            // if (x == row_begin) {
            //     ++y;
            //     ++col_begin;
            //     if (col_begin > col_end) return res;
            //     continue;
            // } else {
            //     --x;
            //     continue;
            // }
        }

        return res;
    }
};

本代码可以通过所有测试用例，编码即为上述思考过程的实现， 即每次将最外圈遍历完成后，内圈的矩阵重复外圈的遍历过程， 接着每次找出每次外圈的规律即可， 即外圈的遍历都为先递增列，随后达到边界递增行，随后达到边界递减列，最后达到边界递减行， 过程中，在每次递增或递减完成要考虑对应边界需要改变，最后思考结束条件即可。

这里值得注意的是，原先结束条件在每次改变边界时进行：

...
++row_begin;
if (row_begin > row_end) return res;
...
--row_end;
if (col_end < col_begin) return res;
...
++col_begin;
if (col_begin > col_end) return res;
...
--row_end;
if (row_end < row_begin) return res;

发现不能通过测试用例[[2,5],[8,4],[0,-1]]，这是因为这样写， 对于这个测试用例来说，值为8的元素不会被遍历到，之前已经结束了， 所以将结束语句的位置调整了一下。

总结：

本题前后思考后觉得，这种问题主要还是要找到规律， 特别在于循环中，代码会按照顺序执行，我们只要找到规律特别是结束条件， 编码中关注当前步规律的编码，先不要去想全局的编码，将当前步编码完成后， 组合起来便是完整的代码，剩下的交给代码按规律顺序执行即可。