螺旋矩阵

问题

给你一个 m 行 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
• -100 <= matrix[i][j] <= 100

方法一

提示💡

• 如果一条边从头遍历到底，则下一条边遍历的起点随之变化
• 选择不遍历到底，可以减小横向、竖向遍历之间的影响
• 一轮迭代结束时，4条边的两端同时收窄 1
• 一轮迭代所做的事情变得很清晰：遍历一个“圈”，遍历的范围收缩为内圈
• 一层层向里处理，按顺时针依次遍历：上、右、下、左。
• 不再形成“环”了，就会剩下：一行或一列，然后单独判断

var spiralOrder = function (matrix) {
    if (matrix.length === 0) return []
    const res = []
    let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
    while (top < bottom && left < right) {
        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])  // 左层
        right--
        top++
        bottom--
        left++  // 四个边界同时收缩，进入内层
    }
    if (top === bottom) // 剩下一行，从左到右依次添加
        for (let i = left; i <= right; i++) res.push(matrix[top][i])
    else if (left === right) // 剩下一列，从上到下依次添加
        for (let i = top; i <= bottom; i++) res.push(matrix[i][left])
    return res
};

方法二

提示💡

• 循环的条件改为： top <= bottom && left <= right
• 每遍历一条边，下一条边遍历的起点被“挤占”，要更新相应的边界
• 注意到，可能在循环途中，突然不再满足循环的条件，即top > bottom或left > right，其中一对边界彼此交错了
• 这意味着所有项都遍历完了，要break了，如果没有及时 break ，就会重复遍历

按照从上右下左的顺序一圈一圈的打印，循环终止条件为任意边界交错。

• 每遍历完一条边，更新相应的边界后，都加上一句if (top > bottom || left > right) break;，避免因没有及时退出循环而导致重复遍历。
• 且，“遍历完成”这个时间点，要么发生在遍历完“上边”，要么发生在遍历完“右边”
• 所以只需在这两步操作之后，加 if (top > bottom || left > right) break 即可

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

换一种条件判断方式，按照从上右下左的顺序一圈一圈的打印，循环终止条件为 res.length === size 矩阵元素总和。

• 遍历完所有项时，res 数组构建完毕。我们可以用 res 数组的长度 等于 矩阵的项的个数，作为循环的结束条件
• 不等于就继续遍历，等于就 break

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
    const row = matrix.length, col = matrix[0].length, size = row * col, res = []
    let top = 0, rigth = col - 1, bottom = row - 1, left = 0 //上右下左四个方向的指针
    while (res.length !== size) {
        // 从左到右, 行不变列变
        for (let i = left; i <= rigth; i++) res.push(matrix[top][i]);
        top++;
        // 从上到下，列不变行变
        for (let i = top; i <= bottom; i++) res.push(matrix[i][rigth]);
        rigth--;
        // 检查是否越界
        if (res.length === size) break;
        // 从右到左，行不变列变
        for (let i = rigth; i >= left; i--) res.push(matrix[bottom][i]);
        bottom--;
        // 从下到上，行变列不变
        for (let i = bottom; i >= top; i--) res.push(matrix[i][left]);
        left++
    }
    return res
};