螺旋矩阵-54

[sl1673495]

给定一个包含  m x n  个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/spiral-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

记录一个 visited 数组，从 0, 0 开始，按照右 -> 下 -> 左 -> 上的方向不断前进，

直到遇到边界或者已经访问过的元素 则切换成下一个方向，每访问一个元素就把结果放入 res 数组中，最终当 res 的长度和矩阵大小一致时，就返回结果。

这里方向用 dirs 表示 4 个方向对应的偏移坐标，通过 currentIndex 指针不断递增来维护当前的方向，由于可能会超出方向数组的长度，所以每次取值都对 4 取余即可。

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
let spiralOrder = function (matrix) {
  let maxY = matrix.length;
  if (!maxY) return [];
  let maxX = matrix[0].length;

  // 记录一个 visited 数组
  // 按照 右 -> 下 -> 左 -> 上 的方向不断前进
  // 直到遇到边界或者已经访问过的元素 则切换成下一个方向
  let dirs = [
    [0, 1], // 右
    [1, 0], // 下
    [0, -1], // 左
    [-1, 0], // 上
  ];

  let currentDirIndex = 0;

  let visited = [];
  for (let y = 0; y < maxY; y++) {
    visited[y] = [];
  }
  let isValid = (y, x) => {
    return y >= 0 && y < maxY && x >= 0 && x < maxX && !visited[y][x];
  };

  let targetLength = maxY * maxX;
  let res = [];

  let helper = (y, x) => {
    let val = matrix[y][x];
    res.push(val);

    if (res.length === targetLength) {
      return res;
    }

    visited[y][x] = true;
    let [diffY, diffX] = dirs[currentDirIndex % 4];
    let nextY = y + diffY;
    let nextX = x + diffX;
    if (!isValid(nextY, nextX)) {
      [diffY, diffX] = dirs[++currentDirIndex % 4];
      nextY = y + diffY;
      nextX = x + diffX;
    }
    helper(nextY, nextX);
  };

  helper(0, 0);

  return res;
};

[Chocolate1999]

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if(!matrix.length) return []
    let n = matrix.length
    let m = matrix[0].length
    let total = n*m
    let top = 0,bottom = n-1
    let left = 0,right = m-1
    let res = []
    while(res.length < total){
        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--
        /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 */
        if(res.length === total) 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
};