算法 - 螺旋矩阵 (Spiral Matrix)

Posted on

1. 题目

给你一个 m × n 的矩阵 matrix，按照螺旋顺序返回矩阵中的所有元素（从外层到内层，顺时针）。

示例:

1
2
3
4
5
6
7
8
9
输入: [[1,2,3],
       [4,5,6],
       [7,8,9]]
输出: [1,2,3,6,9,8,7,4,5]

输入: [[1,2,3,4],
       [5,6,7,8],
       [9,10,11,12]]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

2. 解题思路

螺旋就是「右 → 下 → 左 → 上」四条边循环遍历，每走完一条边就把这条边界向内收缩一格。

维护四个边界：top、bottom、left、right。循环执行：

  1. 向左到右遍历第 top 行，然后 top++（这一行用完）。
  2. 从上到下遍历第 right 列，然后 right--。
  3. 若 top <= bottom，从右到左遍历第 bottom 行，然后 bottom--。
  4. 若 left <= right，从下到上遍历第 left 列，然后 left++。

关键：第 3、4 步在收缩后要再判断边界是否仍合法，否则单行/单列矩阵会重复遍历回去。

  • 时间复杂度：O(m × n)，每个元素访问一次。
  • 空间复杂度：O(1)（不计输出）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function spiralOrder(matrix: number[][]): number[] {
    const res: number[] = [];
    if (matrix.length === 0) return res;

    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // → 顶行
        for (let col = left; col <= right; col++) res.push(matrix[top][col]);
        top++;

        // ↓ 右列
        for (let row = top; row <= bottom; row++) res.push(matrix[row][right]);
        right--;

        // ← 底行（确保还有一行）
        if (top <= bottom) {
            for (let col = right; col >= left; col--) res.push(matrix[bottom][col]);
            bottom--;
        }

        // ↑ 左列（确保还有一列）
        if (left <= right) {
            for (let row = bottom; row >= top; row--) res.push(matrix[row][left]);
            left++;
        }
    }

    return res;
}

console.log(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));
// [1,2,3,6,9,8,7,4,5]

4. 面试延伸

  • 生成螺旋矩阵 II（59 题）：反向操作，按螺旋顺序往空矩阵里填 1..n²，边界收缩逻辑复用。
  • 方向数组写法：用 dirs = [[0,1],[1,0],[0,-1],[-1,0]] + 记录已访问 + 撞墙/撞已访问就转向，是更通用的「螺旋/蛇形」模板，扩展性强但需 O(mn) 的 visited。
  • 模拟类题目没有算法难度，考的是边界严谨性和代码条理性，务必手推 1×n、n×1、1×1 三种退化用例。
  • 相似题：旋转图像（48）、矩阵置零（73） 都在训练你在二维坐标下干净地操作边界。

难度：中等 | LeetCode 54 题 | 边界模拟