0059. Spiral Matrix II¶
题目信息¶
- 题号:
螺旋矩阵 II
- 难度:
Medium
- 主题:
矩阵、模拟、边界收缩
- 原题:
- 重点:
从逐格转向写入,推导到用四条边界描述尚未填充的矩形
题目重述¶
给定正整数 n,构造一个 n × n 矩阵,把整数 1 到 n² 按照从左上角开始、
顺时针向内旋转的螺旋顺序依次写入,并返回该矩阵。
约束为 1 <= n <= 20。
自建示例¶
输入:n = 4
输出:
[[ 1, 2, 3, 4],
[12,13,14, 5],
[11,16,15, 6],
[10, 9, 8, 7]]
先写完外圈的 1..12,再在内部 2 × 2 矩形中写入 13..16。
输入:n = 3
输出:
[[1,2,3],
[8,9,4],
[7,6,5]]
奇数阶矩阵最终只剩中心位置,最后写入 9。
输入:n = 1
输出:[[1]]
起始位置同时也是唯一位置。
C++ 实现¶
#include <vector>
class Solution {
private:
std::vector<std::vector<int>> simulateDirections(int n) {
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
const int rowStep[4] = {0, 1, 0, -1};
const int columnStep[4] = {1, 0, -1, 0};
const int total = n * n;
int row = 0;
int column = 0;
int direction = 0;
for (int value = 1; value <= total; ++value) {
matrix[row][column] = value;
if (value == total) break;
int nextRow = row + rowStep[direction];
int nextColumn = column + columnStep[direction];
bool blocked = nextRow < 0 || nextRow >= n ||
nextColumn < 0 || nextColumn >= n ||
matrix[nextRow][nextColumn] != 0;
if (blocked) {
direction = (direction + 1) % 4;
nextRow = row + rowStep[direction];
nextColumn = column + columnStep[direction];
}
row = nextRow;
column = nextColumn;
}
return matrix;
}
std::vector<std::vector<int>> shrinkBoundaries(int n) {
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
int top = 0;
int bottom = n - 1;
int left = 0;
int right = n - 1;
int value = 1;
while (top <= bottom && left <= right) {
for (int column = left; column <= right; ++column) {
matrix[top][column] = value++;
}
++top;
if (top > bottom) break;
for (int row = top; row <= bottom; ++row) {
matrix[row][right] = value++;
}
--right;
if (left > right) break;
for (int column = right; column >= left; --column) {
matrix[bottom][column] = value++;
}
--bottom;
if (top > bottom) break;
for (int row = bottom; row >= top; --row) {
matrix[row][left] = value++;
}
++left;
}
return matrix;
}
public:
std::vector<std::vector<int>> generateMatrix(int n) {
return shrinkBoundaries(n);
}
};
题解¶
逐格方向模拟¶
最直接的方法真实模拟当前位置和移动方向。每次把 value 写入当前格,再尝试沿右、下、左、上的
当前方向前进一步。下一格越界或已经写入时,方向顺时针旋转一次。
矩阵初始化为 0,而合法写入值是 1..n²,所以 matrix[nextRow][nextColumn] == 0 恰好表示
下一格尚未使用。返回矩阵本身兼作访问标记,不需要额外的 visited 数组。
simulateDirections 在写入 n² 后立即结束,避免为了下一轮而计算不存在的坐标。该方法已经是
O(n²) 时间和 O(1) 额外空间,但每个位置仍要维护方向并判断是否转向。
未写区域压缩¶
完成一圈后,尚未写入的位置不会零散分布,而是严格形成一个更小的矩形。初始未写区域为:
行范围:[0, n-1]
列范围:[0, n-1]
写完外圈后,剩余范围变为:
行范围:[1, n-2]
列范围:[1, n-2]
因此可以用 top、bottom、left、right 四条边界代替当前位置、方向和访问判断。
未写矩形不变量¶
每轮开始时保持:
[top, bottom] × [left, right]
恰好是全部尚未写入的位置;矩形外部已经按螺旋顺序写入连续整数 1..value-1。
当前矩形的外圈按以下顺序写入:
上边:left -> right,随后 top++
右边:top -> bottom,随后 right--
下边:right -> left,随后 bottom--
左边:bottom -> top,随后 left++
每条边写完后立即收缩对应边界,所以刚写入的位置永久离开未写区域。四段首尾相接,组成当前矩形的 顺时针外圈;下一轮只处理它内部的矩形。
写完一条边后,行范围或列范围可能已经为空。此时必须立即结束本轮,防止单行、单列或奇数阶中心点
被再次覆盖。由于 value 每写一个位置才增加一次,而每个位置只离开未写区域一次,最终恰好写入
1..n²,没有遗漏或重复。
状态演化¶
对 n = 4,第一轮从 value = 1 开始:
阶段 |
写入值 |
写入后剩余矩形 |
|---|---|---|
上边 |
|
行 |
右边 |
|
行 |
下边 |
|
行 |
左边 |
|
行 |
第二轮只处理内部 2 × 2 矩形,依次写入 13,14,15,16。
边界统一处理¶
n = 1 时,上边循环写入唯一位置,随后 top > bottom,直接结束。
奇数阶矩阵最终退化为一个中心点,处理方式与 n = 1 完全相同。偶数阶矩阵最终退化为一个
2 × 2 矩形,四段循环正好写完最后一圈。算法不需要单独判断中心位置或矩阵奇偶性。
复杂度分析¶
返回矩阵包含 n² 个位置,任何算法都至少需要 Ω(n²) 时间完成写入。两种方法都恰好访问每个
位置一次,时间复杂度为 O(n²)。
不计必须返回的矩阵,两种方法都只维护常数个变量,额外空间为 O(1)。公开入口调用
shrinkBoundaries,直接利用未写区域始终为矩形的结构。