leetcode--螺旋矩阵
LCR 146.螺旋遍历二维数组
给定一个二维数组
array，请返回「螺旋遍历」该数组的结果。螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
示例 1：
输入：array = [[1,2,3],[8,9,4],[7,6,5]] 输出：[1,2,3,4,5,6,7,8,9]示例 2：
输入：array = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]] 输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]限制：
0 <= array.length <= 1000 <= array[i].length <= 100
原理
初始化边界：
- north, south, east, west 分别表示二维数组的上、下、右、左边界。开始时，
north = 0,south = array.length - 1,east = array[0].length - 1,west = 0，即全覆盖数组的外边界。螺旋遍历：
螺旋遍历从左上角（
north, west）开始，顺时针按“右、下、左、上”的顺序遍历二维数组。第一步： 从左到右遍历，即遍历当前的北边界行。
第二步： 从上到下遍历，即遍历当前的东边界列。
第三步： 从右到左遍历，即遍历当前的南边界行。
第四步： 从下到上遍历，即遍历当前的西边界列。
每一轮螺旋遍历后，都会减少遍历区域的边界：
north++：上边界下移west++：左边界右移south--：下边界上移east--：右边界左移这样，每完成一圈遍历，内层的元素逐步被收录，直到所有元素都被遍历完。
终止条件：
- 当
sum（剩余未遍历元素的数量）为 0 时，表示所有元素都已被访问完，跳出循环。返回结果：
- 最终，
list数组包含了螺旋遍历的所有元素，按顺序返回。时间复杂度：
- 假设数组的维度是
m x n，遍历所有元素的时间复杂度是O(m * n)，因为每个元素都只会被访问一次。空间复杂度：
- 空间复杂度为
O(m * n)，因为需要一个大小为m * n的数组来存储遍历的结果。
代码
class Solution {
public int[] spiralArray(int[][] array) {
// 获取二维数组的行数，即南边界
int south = array.length - 1;
// 如果数组没有行，直接返回空数组
if (south == -1) {
return new int[0];
}
// 获取二维数组的列数，即东边界
int east = array[0].length - 1;
// 如果数组没有列，直接返回空数组
if (east == -1) {
return new int[0];
}
// 计算二维数组中的总元素个数，决定返回数组的大小
int sum = (south + 1) * (east + 1);
// 初始化边界
int north = 0, west = 0;
// 创建存储结果的数组
int[] list = new int[sum];
// count 用来记录当前插入的位置
int count = 0;
// 开始螺旋遍历
while (sum > 0) {
// 从左到右遍历（沿着北边界）
for (int i = west; i <= east; i++) {
list[count++] = array[north][i]; // 将当前元素加入结果数组
sum--; // 每遍历一个元素，减去一个
}
// 如果所有元素已经遍历完，跳出循环
if (sum == 0) {
break;
}
// 从上到下遍历（沿着东边界）
for (int i = north + 1; i <= south; i++) {
list[count++] = array[i][east]; // 将当前元素加入结果数组
sum--; // 每遍历一个元素，减去一个
}
// 如果所有元素已经遍历完，跳出循环
if (sum == 0) {
break;
}
// 从右到左遍历（沿着南边界）
for (int i = east - 1; i >= west; i--) {
list[count++] = array[south][i]; // 将当前元素加入结果数组
sum--; // 每遍历一个元素，减去一个
}
// 如果所有元素已经遍历完，跳出循环
if (sum == 0) {
break;
}
// 从下到上遍历（沿着西边界）
for (int i = south - 1; i > north; i--) {
list[count++] = array[i][west]; // 将当前元素加入结果数组
sum--; // 每遍历一个元素，减去一个
}
// 更新边界，进入内层
north++;
west++;
south--;
east--;
}
// 返回螺旋遍历的结果
return list;
}
}
54.螺旋矩阵
给你一个
m行n列的矩阵matrix，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
原理
初始化边界：
- north, south, east, west 分别表示二维数组的上、下、右、左边界。开始时，
north = 0,south = matrix.length - 1,east = matrix[0].length - 1,west = 0，即全覆盖矩阵的外边界。螺旋遍历：
螺旋遍历从左上角（
north, west）开始，顺时针按“右、下、左、上”的顺序遍历二维矩阵中的元素。第一步： 从左到右遍历，即遍历当前的北边界行。
第二步： 从上到下遍历，即遍历当前的东边界列。
第三步： 从右到左遍历，即遍历当前的南边界行。
第四步： 从下到上遍历，即遍历当前的西边界列。
每完成一圈螺旋遍历后，都会更新边界：
north++：上边界下移west++：左边界右移south--：下边界上移east--：右边界左移这样，每完成一圈遍历，内层的元素逐步被收录，直到所有元素都被遍历完。
终止条件：
- 当
sum（剩余未遍历元素的数量）为 0 时，表示所有元素都已被访问完，跳出循环。返回结果：
- 最终，
list列表包含了矩阵的螺旋顺序遍历结果，按顺序返回。时间复杂度：
- 假设矩阵的维度是
m x n，遍历所有元素的时间复杂度是O(m * n)，因为每个元素只会被访问一次。空间复杂度：
- 空间复杂度为
O(m * n)，因为需要一个大小为m * n的列表来存储遍历的结果。
代码
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
// 获取矩阵的南边界（即最后一行的索引）
int south = matrix.length - 1;
// 获取矩阵的东边界（即最后一列的索引）
int east = matrix[0].length - 1;
// 计算矩阵中元素的总数
int sum = (south + 1) * (east + 1);
// 初始化边界，north 是上边界，west 是左边界
int north = 0, west = 0;
// 用一个列表来存储螺旋遍历的结果
List<Integer> list = new ArrayList<>(south * east);
// 螺旋遍历开始，直到所有元素都被访问
while (sum > 0) {
// 1. 从左向右遍历（沿着北边界）
for (int i = west; i <= east; i++) {
list.add(matrix[north][i]); // 将当前元素加入结果列表
sum--; // 减少未访问的元素数目
}
// 如果所有元素已经遍历完，退出循环
if (sum == 0) {
break;
}
// 2. 从上到下遍历（沿着东边界）
for (int i = north + 1; i <= south; i++) {
list.add(matrix[i][east]); // 将当前元素加入结果列表
sum--; // 减少未访问的元素数目
}
// 如果所有元素已经遍历完，退出循环
if (sum == 0) {
break;
}
// 3. 从右向左遍历（沿着南边界）
for (int i = east - 1; i >= west; i--) {
list.add(matrix[south][i]); // 将当前元素加入结果列表
sum--; // 减少未访问的元素数目
}
// 如果所有元素已经遍历完，退出循环
if (sum == 0) {
break;
}
// 4. 从下到上遍历（沿着西边界）
for (int i = south - 1; i > north; i--) {
list.add(matrix[i][west]); // 将当前元素加入结果列表
sum--; // 减少未访问的元素数目
}
// 更新边界，进入内层
north++; // 上边界下移
west++; // 左边界右移
south--; // 下边界上移
east--; // 右边界左移
}
// 返回螺旋遍历的结果
return list;
}
}
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
原理
初始化：
- 我们首先创建一个大小为
n x n的矩阵ans。- 用
sum变量记录当前要填充的数字，从 1 开始递增。- 使用
row和column变量来指示当前的矩阵填充位置。螺旋顺序填充：
- 每一圈的填充包括四个方向：向右、向下、向左、向上，依次填充矩阵的边界。
- 向右： 从当前的
(row, column)开始，向右填充n个位置。- 向下： 在完成右边的填充后，向下填充
n-1个位置。- 向左： 完成下边的填充后，向左填充
n-2个位置。- 向上： 完成左边的填充后，向上填充
n-3个位置。每次一圈填充后，更新边界，将
n减少 2，以保证下一圈填充在内层矩阵中进行。边界收缩：
- 每次完成一圈的填充后，
column++将列向右移动，准备进行下次填充。- 同时
n -= 2，表示当前有效矩阵的边长减少 2，从而让填充继续进行到内层。终止条件：
- 当
n <= 0时，表示已经填充完所有的元素，退出循环并返回结果矩阵。时间复杂度：
- 假设矩阵的大小为
n x n，所有元素都需要被遍历一次并填充。因此时间复杂度为 O(n²)。空间复杂度：
- 需要一个
n x n的矩阵来存储结果，因此空间复杂度为 O(n²)。
代码
class Solution {
public int[][] generateMatrix(int n) {
// 初始化一个 n x n 的矩阵
int[][] ans = new int[n][n];
// sum 用来记录当前填充的数字，初始为 1
int sum = 1;
// row 和 column 用来记录当前要填充的位置的行和列
int row = 0, column = 0;
// 只要 n > 0，就继续填充
while (n > 0) {
// 1. 从左到右填充当前的北边界
for (int i = 0; i < n; i++) {
ans[row][column++] = sum++; // 填充当前元素，并将列加 1
}
// 向左回退一列，因为 column++ 会使列超出范围
column -= 1;
// 2. 从上到下填充当前的东边界
for (int i = 0; i < n - 1; i++) {
ans[++row][column] = sum++; // 填充当前元素，并将行加 1
}
// 3. 从右到左填充当前的南边界
for (int i = n - 2; i >= 0; i--) {
ans[row][--column] = sum++; // 填充当前元素，并将列减 1
}
// 4. 从下到上填充当前的西边界
for (int i = n - 2; i > 0; i--) {
ans[--row][column] = sum++; // 填充当前元素，并将行减 1
}
// 回到上边界的下一列，并且减少矩阵的规模（边界收缩）
column++;
n -= 2; // 每一圈填充完成后，矩阵的有效边长减少 2
}
// 返回生成的矩阵
return ans;
}
}