54. 螺旋矩阵

题目描述

给你一个 m x n 的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

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

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

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10

出处：LeetCode

解法一：模拟

思路

我们可以模拟螺旋顺序的过程，从左上角开始，按照顺时针的方向遍历矩阵，每次遍历完一行或一列，就将该行或该列置为 null，表示已经遍历过了。

实现

function spiralOrder(matrix: number[][]): number[] {
  const m = matrix.length;
  const n = matrix[0].length;
  const res: number[] = [];

  let top = 0;
  let bottom = m - 1;
  let left = 0;
  let right = n - 1;

  while (top <= bottom && left <= right) {
    for (let i = left; i <= right; i++) {
      if (matrix[top][i] !== null) {
        res.push(matrix[top][i]);
        matrix[top][i] = null;
      }
    }
    for (let i = top + 1; i <= bottom; i++) {
      if (matrix[i][right] !== null) {
        res.push(matrix[i][right]);
        matrix[i][right] = null;
      }
    }
    for (let i = right - 1; i >= left; i--) {
      if (matrix[bottom][i] !== null) {
        res.push(matrix[bottom][i]);
        matrix[bottom][i] = null;
      }
    }
    for (let i = bottom - 1; i > top; i--) {
      if (matrix[i][left] !== null) {
        res.push(matrix[i][left]);
        matrix[i][left] = null;
      }
    }
    top++;
    bottom--;
    left++;
    right--;
  }

  return res;
}

复杂度分析

• 时间复杂度：$O(m \times n)$
• 空间复杂度：$O(1)$

解法二：递归

思路

我们可以将矩阵看成由若干层组成，每一层都是一个环，我们可以递归地遍历每一层环，从而得到整个矩阵的遍历顺序。

实现

function spiralOrder(matrix: number[][]): number[] {
  const res: number[] = [];

  const spiral = (
    matrix: number[][],
    res: number[],
    top: number,
    bottom: number,
    left: number,
    right: number
  ) => {
    if (top > bottom || left > right) {
      return;
    }

    if (top === bottom) {
      for (let i = left; i <= right; i++) {
        res.push(matrix[top][i]);
      }
      return;
    }

    if (left === right) {
      for (let i = top; i <= bottom; i++) {
        res.push(matrix[i][left]);
      }
      return;
    }

    for (let i = left; i < right; i++) {
      res.push(matrix[top][i]);
    }
    for (let i = top; i < bottom; i++) {
      res.push(matrix[i][right]);
    }
    for (let i = right; i > left; i--) {
      res.push(matrix[bottom][i]);
    }
    for (let i = bottom; i > top; i--) {
      res.push(matrix[i][left]);
    }

    spiral(matrix, res, top + 1, bottom - 1, left + 1, right - 1);
  };

  spiral(matrix, res, 0, matrix.length - 1, 0, matrix[0].length - 1);

  return res;
}

复杂度分析

• 时间复杂度：$O(m \times n)$
• 空间复杂度：$O(m \times n)$