TNotes.leetcode

Appearance

0059. 螺旋矩阵 II【中等】

0059. 螺旋矩阵 II【中等】 ​

1. 📝 题目描述 ​

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

示例 1：

img

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

示例 2：

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

提示：

  • 1 <= n <= 20

2. 🎯 s.1 - 模拟（边界收缩） ​

c
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    int** matrix = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++) {
        matrix[i] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }

    int num = 1;
    int top = 0, bottom = n - 1, left = 0, right = n - 1;

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

  while (top <= bottom && left <= right) {
    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
}
py
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        num = 1
        top, bottom, left, right = 0, n - 1, 0, n - 1

        while top <= bottom and left <= right:
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1  # 向右
            top += 1
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1  # 向下
            right -= 1
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    matrix[bottom][i] = num
                    num += 1  # 向左
                bottom -= 1
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    matrix[i][left] = num
                    num += 1  # 向上
                left += 1
        return matrix
  • 时间复杂度：O(n2)，填充 n×n 个元素，每个恰好写入一次
  • 空间复杂度：O(1)，不计输出矩阵，只使用常数额外空间

算法思路：

  • 与「0054 螺旋矩阵」相同的边界收缩思路，区别在于从「读取」变为「写入」
  • 维护四个边界 top, bottom, left, right，按 右→下→左→上 的顺序填入递增数字
  • 每填完一条边，收缩对应边界，向左和向上填充前需判断边界合法性

Discussions