problem

輸入為一個陣列 array，長度至少為 3，元素皆為整數。在不排序 array 的情況下，回傳一個有序陣列，其中包含 array 中最大的三個數字。

sample input:
array = [141, 1, 17, -7, -27, 18, 541]

sample output:
[18, 141, 541]

已知輸出陣列是包含三個數字的有序陣列，所以可以先預設輸出陣列為這樣的狀態：[null, null, null]，然後最終要填入數字變成這樣的結果： [第三大數字, 第二大數字, 最大數字]。

先設定 largest = [null, null, null]，接著開始遍歷輸入陣列，

1. 每個數字 i 依序跟輸出陣列的第三、第二、第一個元素比較。
2. 如果碰到 largest[idx] 為 null，則將 i 填入該位置。如果 i > largest[idx]，則將 i 填入該位置且 largest[idx] 及左邊的元素全部向左移動一個位置。
   例如當 i 為 541，largest 為 [17, 18, 141]，541 > largest[2]，所以將它填入後，largest[2]、largest[1] 原本的數字向左移動，陣列更新為 [18, 141, 541]。

輸入陣列長度為 n，
time: O(n)
space: O(1)

程式碼的部分如同上述步驟，遍歷輸入陣列，與輸出陣列的三個元素比較。接著填入數字及移位的邏輯寫成 shiftAndUpdate 函式，函式從陣列的第一個位置開始看，如果碰到要填入的位置則填入新數字，否則移位 (賦值為後面一個數字)。

function findThreeLargestNumbers(array) {
  const largest = [null, null, null];
  for (const num of array) {
    if (largest[2] === null || num > largest[2]) {
      shiftAndUpdate(largest, num, 2);
    } else if (largest[1] === null || num > largest[1]) {
      shiftAndUpdate(largest, num, 1);
    } else if (largest[0] === null || num > largest[0]) {
      shiftAndUpdate(largest, num, 0);
    }
  }
  return largest;
}

function shiftAndUpdate(array, num, idx) {
  for (let i = 0; i <= idx; i++) {
    if (i === idx) {
      array[i] = num;
    } else {
      array[i] = array[i + 1];
    }
  }
}