螺旋与对角线遍历

螺旋遍历矩阵的思路是什么？

• 维护四个边界 left、right、top、down;
• 按顺时针顺序依次访问: 上行 → 右列 → 下行 → 左列;
• 每访问完一条边界就收缩该边界;
• 任一方向收缩后越界即结束;

螺旋遍历矩阵如何实现？

function spiralOrder(matrix: number[][]): number[] {
  let left = 0;
  let right = matrix[0].length - 1;
  let top = 0;
  let down = matrix.length - 1;
  const result: number[] = [];
  while (true) {
    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
    if (++top > down) break;
    for (let i = top; i <= down; i++) result.push(matrix[i][right]);
    if (--right < left) break;
    for (let i = right; i >= left; i--) result.push(matrix[down][i]);
    if (--down < top) break;
    for (let i = down; i >= top; i--) result.push(matrix[i][left]);
    if (++left > right) break;
  }
  return result;
}

• 时间复杂度: O(m × n);
• 空间复杂度: O(m × n), 保存结果;

如何按对角线顺序遍历矩阵？

• 对角线编号 d = row + col, 共 m + n - 1 条;
• d 为偶数: 沿右上方向遍历 (row 递减, col 递增);
• d 为奇数: 沿左下方向遍历 (row 递增, col 递减);
• 每步只做一次移动, 且优先判断边界:
  • 向右上走: 到最后一列则向下, 到第一行则向右, 否则右上;
  • 向左下走: 到最后一行则向右, 到第一列则向下, 否则左下;

function findDiagonalOrder(mat: number[][]): number[] {
  const m = mat.length;
  const n = mat[0].length;
  const result: number[] = [];
  let row = 0;
  let col = 0;
  for (let i = 0; i < m * n; i++) {
    result.push(mat[row][col]);
    if ((row + col) % 2 === 0) {
      if (col === n - 1) row += 1;
      else if (row === 0) col += 1;
      else {
        col += 1;
        row -= 1;
      }
    } else {
      if (row === m - 1) col += 1;
      else if (col === 0) row += 1;
      else {
        col -= 1;
        row += 1;
      }
    }
  }
  return result;
}

• 时间复杂度: O(m × n);
• 空间复杂度: O(m × n), 保存结果;
• 易错点: 必须把"到最后一列/最后一行"的分支放在最前面, 否则主对角线位置会走错方向;