分析

• 本题的考点：>偏移量技巧。

• 如果当前位置是(x, y)，则该点的上右下左的坐标分别为：(x-1, y), (x, y+1), (x+1, y), (x, y-1)。偏移量为(-1, 0), (0, 1), (1, 0), (0, -1)。

代码

• C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        vector<int> res;
        int n = matrix.size(), m = matrix[0].size();

        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};  // 右，下，左，上
        vector<vector<bool>> st(n, vector<bool>(m));

        for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i++) {
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

• Java

class Solution {
    public int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int n, m;  // 行数，列数

    public List<Integer> spiralOrder(int[][] matrix) {

        n = matrix.length; m = matrix[0].length;

        boolean[][] st = new boolean[n][m];
        for (int i = 0; i < n; i++) Arrays.fill(st[i], false);

        ArrayList<Integer> res = new ArrayList<>();
        int dir = 0, x = 0, y = 0;
        while (res.size() < n * m) {
            if (!st[x][y]) {
                res.add(matrix[x][y]);
                st[x][y] = true;
            }

            int a = x + d[dir][0], b = y + d[dir][1];
            if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) {
                x = a;
                y = b;
            } else dir = (dir + 1) % 4;
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times m)$，n、m为矩阵的行数、列数。

• 空间复杂度：$O(n \times m)$。