leetcode 54. 螺旋矩阵

1. 题解

• 如果一条边从头遍历到底，则下一条边遍历的起点随之变化
• 选择不遍历到底，可以减小横向、竖向遍历之间的影响
• 一轮迭代结束时，4条边的两端同时收窄 1
• 一轮迭代所做的事情变得很清晰：遍历一个“圈”，遍历的范围收缩为内圈
• 一层层向里处理，按顺时针依次遍历：上、右、下、左。
• 不再形成“环”了，就会剩下：一行或一列，然后单独判断

矩阵不一定是方阵
top < bottom && left < right 是循环的条件
无法构成“环”了，就退出循环，退出时可能是这 3 种情况之一：

• top == bottom && left < right —— 剩一行
• top < bottom && left == right —— 剩一列
• top == bottom && left == right —— 剩一项（也算 一行/列）
  处理剩下的单行或单列

因为是按顺时针推入结果数组的，所以

• 剩下的一行，从左至右 依次推入结果数组
• 剩下的一列，从上至下 依次推入结果数组

代码
每个元素访问一次，时间复杂度 O(m*n)，m、n 分别是矩阵的行数和列数

2. 循环

class Solution {
public:
/*
    1. 坚持循环不变量原则，固定规则来遍历
    2. 
*/
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) {
            return res;
        }

        int top = 0;
        int bottom = matrix.size() - 1;
        int left = 0;
        int right = matrix[0].size() - 1;

        while (left < right && top < bottom) {
            // 更新顶行
            for (int i = left; i < right; i++) {
                res.push_back(matrix[top][i]);
            }
            // 更新最右列
            for (int i = top; i < bottom; i++) {
                res.push_back(matrix[i][right]);
            }
            // 更新最底行
            for (int i = right; i > left; i--) {
                res.push_back(matrix[bottom][i]);
            }
            // 更新左列
            for (int i = bottom; i > top; i--) {
                res.push_back(matrix[i][left]);
            }
            left++;
            top++;
            right--;
            bottom--;
        }

        if (top == bottom) {
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }
        } else if (left == right) {
            for (int i = top; i <= bottom; i++) {
                res.push_back(matrix[i][left]);
            }
        }

        return res;
    }
};
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53