LeetCode 剑指 Offer 29. 顺时针打印矩阵
目录
题目描述
题意分析
输入是一个 $m \times n$ 的二维矩阵，要求从左上角出发，沿顺时针方向由外向内把每个元素依次读出来，放进一个一维数组返回。
题目给出的约束信号有三点。第一，矩阵可能不是方阵，行数和列数各自独立，所以不能假设「圈数 = 边长的一半」这类只对方阵成立的结论。第二，每个元素必须恰好输出一次，既不能漏也不能重，这意味着输出数组长度一定是 $m \times n$，可以直接按这个长度预分配。第三，矩阵元素本身没有任何取值限制，不能借助「某个特殊值代表已访问」这种取巧手段。
需要格外留意的边界情形有：矩阵为空，或者第一行为空，此时应当返回空数组而不是访问
matrix[0][0]；矩阵只有一行，读完这一行就该结束，不能再折回来读一次；矩阵只有一列，读完这一列同样要结束。这三种退化情形是绝大多数错误的来源，因为它们恰好落在「一圈没走完就该停」的位置上。
解法：四边界模拟
核心思路
问题关键：已输出区域始终是矩阵外侧的若干圈，剩余元素一定构成连续矩形，因此无需
visited数组，只需四个边界。状态与顺序：
top、bottom、left、right表示当前未输出矩形。每轮依次读取上边、右边、下边、左边，读完一条边立刻向内收缩对应边界。循环不变量：每轮开始时，四个边界围成的矩形内全部未输出，矩形外全部已按顺时针顺序输出。入口条件保证上边存在；上边收缩后，右边从新的
top开始，无剩余行时循环自然为空。再经过右边收缩后，下边或左边可能已经消失，所以读取前必须检查对应边界，防止单行、单列被重复访问。正确性：每轮按顺时针次序输出当前最外圈，并删除该圈对应的边界；四条边通过起点和守卫避开重复角点。剩余区域仍是更小的矩形，不变量继续成立，直到矩形为空，因此每个元素恰好输出一次且顺序正确。
解题步骤
- 空矩阵或空行直接返回空数组。
- 初始化四个边界为整个矩阵，并按元素总数预分配结果。
- 从左到右读取上边，随后
top++；从上到下读取右边，随后right--。- 若仍有行，从右到左读取下边并
bottom--；若仍有列，从下到上读取左边并left++。- 边界相交后结束，返回结果。
口述样例：
[[1,2,3],[4,5,6],[7,8,9]]第一圈输出1,2,3,6,9,8,7,4，边界收缩后只剩中心5，最终得到[1,2,3,6,9,8,7,4,5]。边界检查：单行
[[1,2,3]]读完上边即结束；单列[[1],[2],[3]]由上边和右边读完，不能再读下边或左边。
代码实现
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
int rows = matrix.length;
int cols = matrix[0].length;
int[] res = new int[rows * cols];
int idx = 0;
int top = 0;
int bottom = rows - 1;
int left = 0;
int right = cols - 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
res[idx++] = matrix[top][col];
}
top++;
for (int row = top; row <= bottom; row++) {
res[idx++] = matrix[row][right];
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
res[idx++] = matrix[bottom][col];
}
bottom--;
}
if (left <= right) {
for (int row = bottom; row >= top; row--) {
res[idx++] = matrix[row][left];
}
left++;
}
}
return res;
}
}
func spiralOrder(matrix [][]int) []int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return []int{}
}
rows := len(matrix)
cols := len(matrix[0])
res := make([]int, 0, rows*cols)
top := 0
bottom := rows - 1
left := 0
right := cols - 1
for top <= bottom && left <= right {
for col := left; col <= right; col++ {
res = append(res, matrix[top][col])
}
top++
for row := top; row <= bottom; row++ {
res = append(res, matrix[row][right])
}
right--
if top <= bottom {
for col := right; col >= left; col-- {
res = append(res, matrix[bottom][col])
}
bottom--
}
if left <= right {
for row := bottom; row >= top; row-- {
res = append(res, matrix[row][left])
}
left++
}
}
return res
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子恰好写入结果一次。
- 空间复杂度：$O(1)$，只使用四个边界和结果下标；若计入返回数组则为 $O(mn)$。
关键点总结
- 四边界是“未访问矩形”的最小充分状态，比
visited数组更省空间。- 每输出一条边就立即收缩对应边界，下一条边从收缩后的端点开始，避免重复角点。
- 下边与左边读取前必须重新判断边界，这是单行、单列正确性的关键。
- 面试自测至少覆盖空矩阵、
1×n、m×1、奇偶尺寸矩阵。
易错点总结
- 未判空就访问
matrix[0]：matrix=[]会直接越界。- 下边读取前不检查
top <= bottom：单行矩阵会正向、反向各输出一次。- 左边读取前不检查
left <= right：单列矩阵会被重复输出。- 右边从旧
top开始：右上角会与上边重复；后续边同理要避开已处理角点。- 输出后忘记收缩边界：下一轮会重复同一圈，甚至死循环。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 54. 螺旋矩阵 | 中等 | 与本题完全同构，只是返回 List<Integer> 而非 int[]
|
| 59. 螺旋矩阵 II | 中等 | 把螺旋从「读矩阵」反转成「按序写入矩阵」，且保证是方阵 |