题目

image

暴力

思路：按右、下、左、上的顺序移动，使用数组记录已访问位置，遇到边界或已访问位置就顺时针转向

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> ans;
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        int x = 0, y = 0, d = 0;

        for (int k = 0; k < m * n; ++k) {
            ans.push_back(matrix[x][y]);
            visited[x][y] = true;
            if (k == m * n - 1) break;

            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n ||
                visited[nx][ny]) {
                d = (d + 1) % 4;
            }
            x += dx[d];
            y += dy[d];
        }
        return ans;
    }
};

复杂度： 时间 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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        traverse(matrix, 0, matrix.size() - 1,
                 0, matrix[0].size() - 1, ans);
        return ans;
    }

private:
    void traverse(vector<vector<int>>& a, int top, int bottom,
                  int left, int right, vector<int>& ans) {
        if (top > bottom || left > right) return;

        for (int j = left; j <= right; ++j)
            ans.push_back(a[top][j]);
        for (int i = top + 1; i <= bottom; ++i)
            ans.push_back(a[i][right]);

        if (top < bottom && left < right) {
            for (int j = right - 1; j >= left; --j)
                ans.push_back(a[bottom][j]);
            for (int i = bottom - 1; i > top; --i)
                ans.push_back(a[i][left]);
        }

        traverse(a, top + 1, bottom - 1,
                 left + 1, right - 1, ans);
    }
};

复杂度： 时间 O(mn)，额外空间 O(min(m,n))来自递归栈

最优

思路：维护上、下、左、右四个边界，依次遍历上行、右列、下行、左列，每遍历完一条边就收缩对应边界，边界交错时结束

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        vector<int> ans;

        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; ++j)
                ans.push_back(matrix[top][j]);
            if (++top > bottom) break;

            for (int i = top; i <= bottom; ++i)
                ans.push_back(matrix[i][right]);
            if (--right < left) break;

            for (int j = right; j >= left; --j)
                ans.push_back(matrix[bottom][j]);
            if (--bottom < top) break;

            for (int i = bottom; i >= top; --i)
                ans.push_back(matrix[i][left]);
            ++left;
        }
        return ans;
    }
};

复杂度： 时间 O(mn)，额外空间 O(1)