【数组篇】day21_59. 螺旋矩阵 II

题解：

思路：

• 定义一个与原数组一样大小的数组，用于标记元素是否访问

• 按照题意可知，顺时针螺旋顺序 访问数组，元素依次向 右->下->左->上 方向循环移动，当遇到已标记的元素时，改变移动方向即可

复杂度：

• 时间复杂度：O(n*n) 
• 空间复杂度：O(n*n) 

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];

        // 顺时针旋转 右->下->左->上 循环
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        // 标记元素是否访问
        boolean[][] visited = new boolean[n][n];

        int x = 0, y = 0;
        int dirIndex = 0;
        for (int i = 1; i <= n * n; i++) {
            res[x][y] = i;
            visited[x][y] = true;

            // 下一个元素的坐标
            int nextRow = x + dirs[dirIndex][0], nextColumn = y + dirs[dirIndex][1];
            // 判断是否越界
            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || visited[nextRow][nextColumn]) {
                // 改变位移方向
                dirIndex = (dirIndex + 1) % 4;
            }
            x += dirs[dirIndex][0];
            y += dirs[dirIndex][1];
        }
        return res;
    }
}