LeetCode 59. 螺旋矩阵 II
目录
题目描述
考察公司：小米
题意分析
给定正整数
n，要求生成一个n x n的方阵，按顺时针螺旋的顺序把1到n²依次填进去：从左上角出发向右，撞到边界后向下，再向左，再向上，一圈圈收拢到中心。有两个约束值得单独拎出来。其一是矩阵必然是正方形，行数等于列数，因此不存在长条形矩阵那些「最后剩一行还是剩一列」的不对称情况——但代码仍要能处理收缩到只剩单行或单列的那一刻。其二是填入的数恰好是
1..n²这个连续区间，一个不多、一个不少：这等价于说每个格子被写且只被写一次，写多了会覆盖已填的值，写少了会留下0。这两条合起来把题目变成一道纯粹的「不重不漏」的边界控制题。数据范围
1 <= n <= 20很小，暗示不必考虑效率，考点全在写法的严谨性上。边界情况：
n = 1时答案是[[1]]，只填一个格子，任何多填一次的写法都会在这里暴露；n为奇数时最中心是一个孤立的格子，它既是「单行」也是「单列」；n为偶数时最内层是一个2 x 2的方块，能被四条边正常走完。
解法：四边界螺旋填充
核心思路
问题关键：数字的路径是确定的，但每走完一圈，下一圈的起点和范围都会变化。用方向数组模拟「碰壁转向」需要额外判断是否访问过，状态更分散。
为什么选四边界：任意时刻，未填写区域都是一个矩形。用
top、bottom、left、right表示它，按上、右、下、左依次填写四条边；每完成一条边，就把对应边界向内收缩一格。这与 54 题螺旋读取是同一骨架，只是把读取改成写入。不变量：每轮开始时，边界矩形内的格子全部未填，矩形外的格子已经按顺时针顺序填好，
value是下一个要写入的数。四条边处理完后，未填区域仍是一个更小的矩形，因此不变量可以逐圈维持。正确性：每条边只填写当前未填矩形的外沿，随后立即移出该边；因此不同轮次不会重复访问同一格。边界交叉时未填矩形为空，所有
n²个位置都已按路径依次写入1..n²。收尾条件：上边、右边收缩后，矩形可能已经退化为空。填写下边前要检查
top <= bottom，填写左边前要检查left <= right，否则单行或单列会被重复填写。
解题步骤
- 创建
n x n矩阵，初始化四条边界和value = 1。- 从左到右填写上边，随后
top++。- 从上到下填写右边，随后
right--。- 若仍有行，从右到左填写下边，随后
bottom--。- 若仍有列，从下到上填写左边，随后
left++。- 重复上述过程，直到上下或左右边界交叉。
口述样例：
n = 3时，第一圈依次填入1,2,3 | 4,5 | 6,7 | 8，边界收缩后只剩中心格，再填9，得到[[1,2,3],[8,9,4],[7,6,5]]。
代码实现
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int top = 0;
int bottom = n - 1;
int left = 0;
int right = n - 1;
int value = 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
matrix[top][col] = value++;
}
top++;
for (int row = top; row <= bottom; row++) {
matrix[row][right] = value++;
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
matrix[bottom][col] = value++;
}
bottom--;
}
if (left <= right) {
// 左边界仍存在时，再从下到上填充左边。
for (int row = bottom; row >= top; row--) {
matrix[row][left] = value++;
}
left++;
}
}
return matrix;
}
}
func generateMatrix(n int) [][]int {
matrix := make([][]int, n)
for i := 0; i < n; i++ {
matrix[i] = make([]int, n)
}
top := 0
bottom := n - 1
left := 0
right := n - 1
value := 1
for top <= bottom && left <= right {
for col := left; col <= right; col++ {
matrix[top][col] = value
value++
}
top++
for row := top; row <= bottom; row++ {
matrix[row][right] = value
value++
}
right--
if top <= bottom {
for col := right; col >= left; col-- {
matrix[bottom][col] = value
value++
}
bottom--
}
if left <= right {
// 边界检查避免单行或单列时重复填充。
for row := bottom; row >= top; row-- {
matrix[row][left] = value
value++
}
left++
}
}
return matrix
}
复杂度分析
- 时间复杂度：$O(n^2)$。每个格子恰好填写一次，且输出本身就有
n²个元素。- 空间复杂度：$O(1)$。除返回矩阵外只使用四条边界和一个计数器。
关键点总结
- 四条边界描述的是「尚未处理的矩形」，每填一条边就立即收缩。
- 遍历方向必须固定为右、下、左、上，四个角只由先到达的那条边填写。
- 下边和左边开始前必须重新检查边界，处理单行、单列和中心格。
- 证明不重不漏：每条已填边立即移出未填矩形，边界最终覆盖并移除全部
n²个格子。- 方向模拟也能完成，但需要转向和已填判断；四边界更适合面试现场书写。
易错点总结
- 下边、左边不做二次边界判断：
n = 1时中心格会被重复覆盖。- 填右边仍从旧
top开始：右上角会写两次；后续边同理要避开已处理的角。- 填完边后忘记收缩对应边界，会重复填写甚至死循环。
- 下边、左边方向写反，会破坏顺时针次序；
n = 3是最小的有效检查样例。- Go 的二维切片只创建外层还不够，每一行都必须单独
make，否则写入时越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 54. 螺旋矩阵 | 中等 | 同一骨架的读取版，矩阵是 m x n 长方形，退化判断更易触发 |
| 剑指 Offer 29. 顺时针打印矩阵 | 简单 | 54 的等价题，需额外处理空矩阵输入 |
| 48. 旋转图像 | 中等 | 同样按层处理方阵，但要求原地四点轮换而非顺序填数 |
| 面试题 01.07. 旋转矩阵 | 中等 | 48 的等价题，可用转置加翻转替代按层轮换 |