主題: 學習筆記

LeetCode 1732：TypeScript 單次掃描找最高海拔

用目前海拔與最高海拔兩個狀態，完成 O(n) 時間、O(1) 額外空間的單次掃描。

這題不需要記住每一站的海拔。維護兩個數值就夠了：目前海拔與目前看過的最高海拔。每經過一段路，先更新目前海拔，再更新最高海拔。

題目

對應原題：LeetCode 1732：Find the Highest Altitude

自行車從高度 0 出發。gain[i] 是第 i 段路程帶來的高度變化。回傳旅途中曾到達的最高高度，起點也算。

例如，[-5, 1, 5, 0, -7] 對應的高度依序是 [0, -5, -4, 1, 1, -6]，答案為 1。

不必建立所有海拔

可以先建立一個陣列，放入每一站的海拔，再從中找最大值。不過每走一段路，只會多出一個新海拔，而我們只關心它是否超過目前最高值。

保留目前海拔與最高海拔，就能在讀取每個 gain 後立刻完成判斷。

function largestAltitude(gain: number[]): number {
  let currentAltitude = 0;
  let maxAltitude = currentAltitude;

  for (let index = 0; index < gain.length; index += 1) {
    currentAltitude += gain[index];
    maxAltitude = Math.max(maxAltitude, currentAltitude);
  }

  return maxAltitude;
}

為什麼正確

每次迴圈開始時，currentAltitude 是目前所在位置的海拔，maxAltitude 是起點到目前位置之間的最高海拔。

加上 gain[index] 後，currentAltitude 變成下一個位置的海拔。接著用 Math.max() 比較新海拔與舊的最高海拔，因此 maxAltitude 也涵蓋下一個位置。迴圈結束時，它看過起點與所有路段終點，回傳值就是全程最高海拔。

起點的高度為 0，所以一開始就要把 maxAltitude 設為 0。若所有路段都往下，答案仍然是 0。

最小驗證

import assert from "node:assert/strict";

assert.strictEqual(largestAltitude([-5, 1, 5, 0, -7]), 1);
assert.strictEqual(largestAltitude([-4, -3, -2, -1, 4, 3, 2]), 0);
assert.strictEqual(largestAltitude([3, -2, 4, -10]), 5);

第二個案例會檢查是否把起點納入答案。第三個案例則確認最高點不一定在最後一站。

複雜度

陣列只掃描一次，時間是 O(n)。函式只使用 currentAltitude 與 maxAltitude 兩個數值，額外空間是 O(1)。

這兩個值是會更新的變數，不是常數；空間複雜度看的是需要多少個儲存位置，而不是變數是否改變。

常見陷阱

• 忘記起點高度 0，全程下降時回傳負數。
• 先比較最高海拔，後更新目前海拔，漏掉剛抵達的新位置。
• 回傳最後海拔，而不是全程最高海拔。
• 建立完整海拔陣列，卻沒有需要使用其中的中間值。

可遷移的觀念

這是串流掃描的常見分工。currentAltitude 記錄目前狀態，maxAltitude 記錄到目前為止的最佳結果。只要資料可依序讀取，通常不必保存所有歷史資料。

外部參考連結

• LeetCode 1732：Find the Highest Altitude：原始題目、範例與限制。
• TypeScript Handbook：More on Functions：函式參數與回傳型別語法。
• Node.js：assert.strictEqual()：使用 assertion 驗證預期結果。