【数据结构与算法】力扣 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×n 的矩阵，用 0 填充表示未填充的位置。

• 定义边界：top、bottom、left 和 right，分别代表当前矩阵的上、下、左、右边界。

• 用一个变量 num 记录当前要填入的数字，从 1 开始。

• 按照顺时针方向填充矩阵，具体顺序为：

  • 从左到右填充顶部行，然后将 top 边界向下移动。
  • 从上到下填充右侧列，然后将 right 边界向左移动。
  • 从右到左填充底部行，然后将 bottom 边界向上移动。
  • 从下到上填充左侧列，然后将 left 边界向右移动。

• 重复上述步骤，直到填满所有位置。

/*** @param {number} n* @return {number[][]}*/
const generateMatrix = function(n) {const matrix = Array.from({ length: n }, () => Array(n).fill(0));let top = 0, bottom = n - 1;let left = 0, right = n - 1;let num = 1;while (num <= n * n) {// 从左到右填充for (let i = left; i <= right; i++) {matrix[top][i] = num++;}top++;// 从上到下填充for (let i = top; i <= bottom; i++) {matrix[i][right] = num++;}right--;// 从右到左填充if (top <= bottom) {for (let i = right; i >= left; i--) {matrix[bottom][i] = num++;}bottom--;}// 从下到上填充if (left <= right) {for (let i = bottom; i >= top; i--) {matrix[i][left] = num++;}left++;}}return matrix;
};

思路拓展

螺旋矩阵相关的问题，都可以通过一层一层遍历，通过一行一列、一行一列的顺序处理每个元素。

而且遍历过程中一定有一个规律，就是总有一个坐标是不变的，而另一个坐标在变。

解决螺旋矩阵题目时，可以总结出一些通用的解题方法和步骤。这些方法适用于填充矩阵或读取矩阵元素的螺旋顺序。

类似的题型见：螺旋矩阵

通用方法总结

1. 定义边界变量：

   • 使用 top、bottom、left 和 right 四个变量来表示当前矩阵的边界。
   • top 表示当前未填充区域的最上边行索引，bottom 表示最下边行索引。
   • left 表示未填充区域的最左边列索引，right 表示最右边列索引。
   • 这些边界变量随着螺旋填充或遍历逐渐收缩，直到遍历完成整个矩阵。

2. 按照顺时针方向遍历或填充：

   • 按照顺时针的顺序进行：从左到右（填充 top 行），从上到下（填充 right 列），从右到左（填充 bottom 行），从下到上（填充 left 列）。
   • 每次填充后，相应地缩小边界（如 top++、bottom--、left++、right--）。

3. 边界条件判断：

   • 在每次填充新的行或列之前，判断当前的 top <= bottom 和 left <= right，确保当前边界仍然有效，防止重复填充或越界。
   • 这些判断可以避免在矩阵维度不对称时（如奇数维度矩阵）多次填充同一行或列。

4. 循环控制条件：

   • 通常使用一个 while 循环，当填充的数字还未达到矩阵总数 ( n^2 ) 时，继续循环。
   • 如果是读取矩阵中的元素，循环直到所有元素都遍历完。

解决螺旋矩阵问题的通用步骤

1. 初始化矩阵和边界变量：

   • 创建一个合适大小的矩阵，用来存放填充结果。
   • 初始化 top、bottom、left 和 right。

2. 进行螺旋顺序填充或读取：

   • 按照顺时针顺序进行：从左到右，从上到下，从右到左，从下到上。
   • 每次填充或读取后，收缩相应的边界。

3. 更新填充条件和检查边界：

   • 进行边界检查，确保没有重复填充。

4. 返回结果：

   • 返回填充完的矩阵，或者返回读取顺序得到的结果。

注意事项

• 边界条件的处理：确保在每次改变边界时进行有效的判断，避免多次填充同一行或列。
• 初始化矩阵大小：根据题目的输入大小 ( n ) 确保矩阵初始化正确。
• 边界收缩顺序：每次遍历结束后，适时更新 top、bottom、left 和 right 的值。