Description

算法步骤

1. 设定t,b,l,r四个边界分别代表上、下、左、右，同时也代表一个圈，每次将整个圈遍历完，然后更新边界，缩小这个圈。

• 标记解法：将已经访问过的元素标记为 Infinity，不需要判断越界的情况。
• 不标记解法：在遍历的过程当中还要判断越界的情况，比如只有一行，或者一列，t更新后，t>b，或者l更新后，l>r，那么就说明没有下一圈了，直接退出。不然会导致重复遍历。

// 标记解法
function spiralOrder(matrix: number[][]): number[] {
  const ans: number[] = [];
  const m = matrix.length;
  const n = matrix[0].length;
  const visit = (i: number, j: number) => {
    if (matrix[i][j] !== Infinity) {
      ans.push(matrix[i][j]);
      matrix[i][j] = Infinity;
    }
  };

  let t = 0;
  let b = m - 1;
  let l = 0;
  let r = n - 1;

  while (t <= b && l <= r) {
    for (let i = l; i <= r; i++) {
      visit(t, i);
    }
    t++;

    for (let i = t; i <= b; i++) {
      visit(i, r);
    }
    r--;

    for (let i = r; i >= l; i--) {
      visit(b, i);
    }
    b--;

    for (let i = b; i >= t; i--) {
      visit(i, l);
    }
    l++;
  }

  return ans;
};

// 不标记解法
function spiralOrder1(matrix: number[][]): number[] {
  const ans: number[] = [];
  const m = matrix.length;
  const n = matrix[0].length;

  let t = 0;
  let b = m - 1;
  let l = 0;
  let r = n - 1;

  while (t <= b && l <= r) {
    for (let i = l; i <= r; i++) {
      ans.push(matrix[t][i]);
    }
    t++;
    for (let i = t; i <= b; i++) {
      ans.push(matrix[i][r]);
    }
    r--;
    for (let i = r; i >= l; i--) {
      ans.push(matrix[b][i]);
    }
    b--;
    for (let i = b; i >= t; i--) {
      ans.push(matrix[i][l]);
    }
    l++;
  }

  return ans;
};
Copy