59.螺旋矩阵II

​ 力扣题目链接

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

​ 示例 1：

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

​ 示例 2：

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

​ 提示：

​ 1 <= n <= 20

​ 来源：力扣（LeetCode） ​ 链接：https://leetcode.cn/problems/spiral-matrix-ii

思路

​ 模拟矩阵的生成。需要特别注意循环不变原则。

​ （1）从左到右填充最上层（闭区间）

​ （2）从上到下填充最右层（跳到下一个目标位置的闭区间）

​ （3）从右到左填充最下层（跳到下一个目标位置的闭区间）

​ （4）从下到上填充最左层（跳到下一个目标位置的闭区间）

​ 在纸上很容易画出该过程。每个颜色为一次填充。

实现代码：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
        //四个标记点，分别代表边界，是边界的具体位置
		int left = 0, top = 0;
		int right = n - 1, bottom = n - 1;
        //填充的角标计数值
		int index = 1;
        //二维数组位置，i为行，j为列
		int i = 0, j = 0;
        //初始化存储答案的容器
		vector<vector<int>> ans(n, vector<int>(n, 0));
        //如果顶部小于等于底部，左部小于等于有部才进入循环，填充完成时矩阵不满足此关系
		while (top <= bottom || left <= right)
		{
            //判断是否在左上角，如果是就填充这一行，从左到右
			if (j == left && i == top)
			{
                //填充整行还未填充的位置，用right来界定是否到达位置
				while (j <= right)
				{
                    //更新相应数据
					ans[i][j++] = index;
					index++;
				}
                //填充完成之后更新数据，为下次循环做准备
                //此时右上角应该填充完成，故顶部移到下一行
				top++;
                //更新填充元素的位置为下一个
				i++;
                //由于上面执行了j++这里需要修正回到正确的位置
				j--;
			}
            //判断是否在未填充的位置的右上角，如果是就填充这一列，从上到下
			if (i == top && j == right)
			{
                //填充整列还未填充的位置，用bottom来界定是否到达位置
				while (i <= bottom)
				{
                    //更新相应数据
					ans[i++][j] = index;
					index++;
				}
                //填充完成之后更新数据，为下次循环做准备
                //此时右下角应该填充完成，故右部移到左边一列
				right--;
                //更新填充元素的位置为左边一个
				j--;
                //由于上面执行了i++这里需要修正回到正确的位置
				i--;
			}
            //判断是否在未填充的位置的右下角，如果是就填充这一列，从右到左
			if (i == bottom && j == right)
			{
                //填充整行还未填充的位置，用left来界定是否到达位置
				while (j >= left)
				{
                    //更新相应数据
					ans[i][j--] = index;
					index++;
				}
                //填充完成之后更新数据，为下次循环做准备
                //此时左下角应该填充完成，故底部移到上面一列
				bottom--;
                //更新填充元素的位置为上边一个
				i--;
                //由于上面执行了j--这里需要修正回到正确的位置
				j++;
			}
            //判断是否在未填充的位置的左下角，如果是就填充这一列，从下到上
			if (i == bottom && j == left)
			{
                //填充整列还未填充的位置，用top来界定是否到达位置
				while (i >= top)
				{
                    //更新相应数据
					ans[i--][j] = index;
					index++;
				}
                //填充完成之后更新数据，为下次循环做准备
                //此时右上角应该填充完成，故左部移到右边一列
				left++;
                //更新填充元素的位置为右边一个
				j++;
                //由于上面执行了i++这里需要修正回到正确的位置
				i++;
			}
        //上述已形成闭环，没有区间冲突的问题
		}

		return ans;
	}
};
  • 时间复杂度 : 模拟遍历二维矩阵的时间
  • 空间复杂度

不带注释：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
        //四个标记点，分别代表边界，是边界的具体位置
		int left = 0, top = 0;
		int right = n - 1, bottom = n - 1;
        //填充的角标计数值
		int index = 1;
        //二维数组位置，i为行，j为列
		int i = 0, j = 0;
		vector<vector<int>> ans(n, vector<int>(n, 0));
        //如果顶部小于等于底部，左部小于等于有部才进入循环，填充完成时矩阵不满足此关系
		while (top <= bottom || left <= right)
		{
            //判断是否在左上角，如果是就填充这一行，从左到右
			if (j == left && i == top)
			{
				while (j <= right)
				{
					ans[i][j++] = index;
					index++;
				}
				top++;
				i++;
				j--;
			}
            //判断是否在未填充的位置的右上角，如果是就填充这一列，从上到下
			if (i == top && j == right)
			{
				while (i <= bottom)
				{
                    //更新相应数据
					ans[i++][j] = index;
					index++;
				}
				right--;
				j--;
				i--;
			}
            //判断是否在未填充的位置的右下角，如果是就填充这一列，从右到左
			if (i == bottom && j == right)
			{
				while (j >= left)
				{
					ans[i][j--] = index;
					index++;
				}
				bottom--;
				i--;
				j++;
			}
            //判断是否在未填充的位置的左下角，如果是就填充这一列，从下到上
			if (i == bottom && j == left)
			{
				while (i >= top)
				{
					ans[i--][j] = index;
					index++;
				}
				left++;
				j++;
				i++;
			}
		}
		return ans;
	}
};