59.螺旋矩阵II

题目简介

题目链接

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

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

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

思路

这道题很容易把人绕晕进去，如果找不到一个统一的写法，会产生大量的逻辑判断。下面我给出一个很巧妙的方法，不光是对这种正方形有用，同时也适用于长方形

我们访问的顺序就是最外面这一圈，像是剥洋葱一样，一条一条的把边剥开，然后每次处理的就是一个新的矩形，代码其实非常好理解，up,down, left, right分别表示矩形的上下左右边界，count表示当前要填入的数字，vec是结果矩阵

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int up = 0, down = n - 1, left = 0, right = n - 1;
        int count = 1;
        vector<vector<int>> vec(n, vector<int>(n, 0));
        while (1) {
            for (int i = left; i <= right; i++) vec[up][i] = count++;
            if (++up > down) break;
            for (int i = up; i <= down; i++) vec[i][right] = count++;
            if (--right < left) break;
            for (int i = right; i >= left; i--) vec[down][i] = count++;
            if (--down < up) break;
            for (int i = down; i >= up; i--) vec[i][left] = count++;
            if (++left > right) break;
        }
        return vec;
    }
};

时间复杂度O(n^2)，空间复杂度O(n^2)