problem

輸入為一個長寬為 m * n (m 可以等於 n) 的雙層陣列，將其中所有的元素以螺旋的順序放入另一陣列回傳。

這裡的螺旋順序指的是從雙層陣列的左上角開始向右，以螺旋的方式看過每個陣列中的每個元素。

sample input:
array = [
  [1,   2,   3,   4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10,   9,   8,   7]
]

sample output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

解這題的其中一個想法是追蹤目前遍歷陣列的方向，例如一開始的方向是向右，直到碰到底變成向下，再碰到底變成向左...以此類推。

或者另外一種想法是，要用螺旋順序遍歷陣列，代表先看過整個陣列的外圍。
1       2       3     4
12   13   14     5
11   16   15     6
10     9     8       7

接著再看陣列剩餘部份的外圍...如此一圈一圈向內，直到看完整個陣列，且不論雙層陣列長寬多少，都適用這個規則。也就是說，只要知道如何遍歷最外圍，就可以遍歷整個陣列。

要遍歷外圍，首先利用幾個變數來指向陣列的首列 (sR)、末列 (eR)、首行 (sC)、末行 (eC)。而且這幾個變數可以直接用雙層陣列的長度來表達。

      sC       eC
      ↓           ↓
sR → 1       2       3     4
        12   13   14     5
        11   16   15     6
eR → 10     9     8      7

接著，
看過 sC 到 eC，在 sR 上的數字 (1, 2, 3, 4)
看過 (sR + 1) 到 eR，在 eC 上的數字 (5, 6, 7)
看過 (eC - 1) 到 sC，在 eR 上的數字 (8, 9 10)
看過 (eR - 1) 到 (sR + 1)，在 sC 上的數字 (11, 12)

此時已經看完整個雙層陣列的最外圍，接下來只要把同樣的邏輯重複在內層進行，也就是將 sR、sC 加一，eR、eC 減一，進行上方的步驟。直到 sR、eR 或 sC、eC 交錯，就可以知道已經看完所有數字。

最後再考慮可能會有首列末列或首行末行重疊的情況，例如下方陣列，最後會只剩下一列數字要看。這時候如果還以四邊形的方式遍歷，就會出現重複。因此在遍歷每一圈外圍的下邊和左邊時，再加入 sR == eR 和 sC == eC 的判斷。
[
  [1, 1, 1, 1],
  [2, 2, 2, 2],
  [3, 3, 3, 3]
]

N 為雙層陣列中所有元素的數量
time: O(N)
space: O(N)

迴圈的寫法：

function spiralTraverse(array) {
  const result = [];
  let startRow = 0, endRow = array.length - 1;
  let startCol = 0, endCol = array[0].length - 1;

  while (startRow <= endRow && startCol <= endCol) {
    for (let col = startCol; col <= endCol; col++) {
      result.push(array[startRow][col]);
    }

    for (let row = startRow + 1; row <= endRow; row++) {
      result.push(array[row][endCol]);
    }

    for (let col = endCol - 1; col >= startCol; col--) {
      // 處理只剩一列的特殊情況
      if (startRow === endRow) break;
      result.push(array[endRow][col]);
    }

    for (let row = endRow - 1; row >= startRow + 1; row--) {
      // 處裡只剩一行的特殊情況
      if (startCol === endCol) break;
      result.push(array[row][startCol]);
    }

    startRow++;
    endRow--;
    startCol++;
    endCol--
  }

  return result;
}

遞迴的寫法：

function spiralTraverse(array) {
  const result = [];
  spiralFill(array, 0, array.length - 1, 0, array[0].length - 1, result);
  return result;
}

function spiralFill(array, startRow, endRow, startCol, endCol, result) {
  if (startRow > endRow || startCol > endCol) return;

  for (let col = startCol; col <= endCol; col++) {
    result.push(array[startRow][col]);
  }

  for (let row = startRow + 1; row <= endRow; row++) {
    result.push(array[row][endCol]);
  }

  for (let col = endCol - 1; col >= startCol; col--) {
    if (startRow === endRow) break;
    result.push(array[endRow][col]);
  }

  for (let row = endRow - 1; row >= startRow + 1; row--) {
    if (startCol === endCol) break;
    result.push(array[row][startCol]);
  }

  spiralFill(array, startRow + 1, endRow - 1, startCol + 1, endCol - 1, result);
}