螺旋矩阵和旋转图像怎样做？

简答

螺旋矩阵是把一个 m × n 的矩阵从左上角开始，按顺时针一圈圈往里读出来。旋转图像是把一个 n × n 的矩阵顺时针转 90 度，而且要原地修改，不能另开一个矩阵。

螺旋矩阵用四个变量记住还没读的区域：top、bottom、left、right。先沿 top 这一行从左读到右，读完 top 加 1；再沿 right 这一列往下读，right 减 1；然后沿 bottom 从右往左，bottom 减 1；最后沿 left 往上，left 加 1。这样一圈圈往里收，直到边界交错。

旋转图像有一个好记的拆法：顺时针转 90 度等于先转置，也就是沿左上到右下的对角线把 [i][j] 和 [j][i] 互换，再把每一行左右翻转。两步都是原地交换，时间 O(n²)，额外空间 O(1)。

要注意，螺旋矩阵走完上边和右边以后，矩阵可能只剩一行或一列，走下边和左边之前要再检查 top <= bottom、left <= right，否则会重复读。转置时只能交换对角线一侧的元素，j 从 i + 1 开始，全部交换一遍就换回去了。

螺旋矩阵

看走下边和左边之前的两个 if。

JavaScript

function spiralOrder(matrix) {
  const result = [];
  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let j = left; j <= right; j++) result.push(matrix[top][j]);
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}

function rotate(matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (const row of matrix) row.reverse();
  return matrix;
}

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

console.log(JSON.stringify(rotate([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))); // [[7,4,1],[8,5,2],[9,6,3]]
console.log(JSON.stringify(rotate([[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]))); // [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
console.log(JSON.stringify(rotate([[1]]))); // [[1]]

为什么那两个 if 不能省？看只有一行的 [[1, 2, 3]]。上边读完 1、2、3 以后 top 变成 1，比 bottom 的 0 大，右边那一列的循环一次都不执行。如果不检查就去读下边，会把同一行倒着再读一遍，得到 1,2,3,2,1。只有一列时同理，左边那一列会被重复读。前两步不用检查，因为 while 条件已经保证了这一圈开始时边界没有交错。

为什么转置加翻转就是顺时针旋转

顺时针转 90 度时，原来第 i 行第 j 列的元素，会跑到第 j 行、倒数第 i 列，也就是 [j][n - 1 - i]。转置先把 [i][j] 送到 [j][i]，每行左右翻转再把 [j][i] 送到 [j][n - 1 - i]，两步合起来正好一致。

看第一个例子，第一行 1,2,3 转置后变成第一列，第一行变成 1,4,7，翻转后是 7,4,1，就是旋转后的第一行。row.reverse() 会原地修改数组，正好满足题目“原地旋转”的要求。

常见追问

逆时针转 90 度怎么做？

先转置，再上下翻转，也就是把整个行数组 reverse 一下。也可以先把每行左右翻转再转置。转 180 度就是先上下翻转，再把每行左右翻转。

不拆成两步，能一次到位吗？

能。从外到内一圈圈处理，每圈里四个位置的元素组成一组，[i][j]、[j][n-1-i]、[n-1-i][n-1-j]、[n-1-j][i]，用一个临时变量让它们依次挪一格。时间和空间与两步法一样，只是下标容易写错。

螺旋矩阵 II 要求按螺旋顺序填 1 到 n² 怎么做？

边界收缩的写法完全一样，只是把读取 matrix[i][j] 改成写入一个递增的计数器。