主題: 學習筆記

LeetCode 121：TypeScript 買賣股票的最佳時機

從雙層迴圈枚舉交易，改為一次掃描追蹤最低買入價，說明雙指標版本的正確性與 O(n) 複雜度。

這題常見的第一個解法是枚舉買入日和賣出日。它不難寫，也不會算錯，但資料一大就太慢。把「到目前為止最低的買入價格」留在狀態裡，就能把兩層迴圈收斂成一次掃描。

題目

對應原題：LeetCode 121：Best Time to Buy and Sell Stock

給定陣列 prices，prices[i] 是第 i 天的股價。只能買賣各一次，且買入日必須早於賣出日。回傳最大獲利；若沒有正數獲利，回傳 0。

暴力解會檢查每一組交易

function maxProfitBruteForce(prices: number[]): number {
  let bestProfit = 0;

  for (let buyDay = 0; buyDay < prices.length; buyDay += 1) {
    for (let sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
      bestProfit = Math.max(bestProfit, prices[sellDay] - prices[buyDay]);
    }
  }

  return bestProfit;
}

這個版本列出每個合法的買入、賣出組合，再保留最大價差。邏輯直接，也正確。問題在於每個買入日都會重新走過後面的賣出日。最壞情況有 n(n - 1) / 2 組交易，時間是 O(n²)，額外空間是 O(1)。

題目允許的陣列長度可達 10^5。兩層迴圈會產生約五十億組比較，不能接受。

雙指標版本

function maxProfit(prices: number[]): number {
  let p1 = 0;
  let p2 = 1;
  let bestProfit = 0;

  while (p2 < prices.length) {
    if (prices[p1] > prices[p2]) {
      p1 = p2;
    } else {
      bestProfit = Math.max(bestProfit, prices[p2] - prices[p1]);
    }

    p2 += 1;
  }

  return bestProfit;
}

這個想法是正確的。p1 保留目前最適合的買入日，p2 依序當作賣出日。當 prices[p2] 更低時，舊的買入日不必再保留。未來若在某天賣出，以較低的 prices[p2] 買入，獲利只會相同或更高。

這裡不是跳過中間的日期。p2 仍逐日往右走；被淘汰的是較高的舊買入價。這個差別很重要，因為它正好說明為何演算法是 O(n)，而不是少做一些不明確的比較。

原本的版本在遇到新低價後會把 p2 重設為 p1 + 1。直接讓 p2 在每輪最後加一，行為相同，迴圈條件也更短。

一個更容易說明的等價寫法

這不是更快的演算法。兩個版本都是 O(n) 時間和 O(1) 額外空間。差別只在於狀態名稱。

function maxProfit(prices: number[]): number {
  let minPrice = prices[0];
  let bestProfit = 0;

  for (let day = 1; day < prices.length; day += 1) {
    bestProfit = Math.max(bestProfit, prices[day] - minPrice);
    minPrice = Math.min(minPrice, prices[day]);
  }

  return bestProfit;
}

minPrice 直接表示目前看過的最低價格。處理第 day 天時，先用先前日期的最低價格計算「今天賣出」的最大獲利，再把今天納入最低價格。這種寫法少了指標重設，面試時通常更容易解釋。

為什麼一次掃描正確

在處理第 day 天之前，minPrice 是 prices[0] 到 prices[day - 1] 的最小值，bestProfit 則是所有賣出日在 day 之前的最大合法獲利。

若今天賣出，最好的買入價格必定是先前看過的最低價格，因此 prices[day] - minPrice 已涵蓋所有以今天為賣出日的最佳交易。更新 bestProfit 後，再以今天價格更新 minPrice，上述條件會在下一輪繼續成立。

第一天沒有更早的日期可買，因此從索引 1 開始。題目保證陣列至少有一個元素。若價格一路下降或相同，所有價差都不會讓 bestProfit 超過初始值 0，結果符合題意。

最小驗證

import assert from "node:assert/strict";

assert.equal(maxProfit([1, 1, 1]), 0);
assert.equal(maxProfit([7, 6, 5, 4, 3]), 0);
assert.equal(maxProfit([12, 9534, 433, 121, 3463, 461, 22, 534, 1, 1457, 2, 3321]), 9522);
assert.equal(maxProfit([2]), 0);

node:assert/strict 會在比較失敗時拋出錯誤，比只看 console.log() 更適合作為最小驗證。Node.js 的 assert 文件也列出這種嚴格比對的用法。

複雜度與可遷移觀念

暴力解的時間是 O(n²)，最佳化版本是 O(n)。兩者都只使用固定數量的數值變數，因此額外空間是 O(1)。

重點不是股票題本身，而是將「過去所有買入候選」壓縮成一個最低值。遇到某個新低價時，不必保留每個舊價格，因為它們對未來賣出日都不會更好。這個淘汰規則會再出現在區間最佳化與單調資料結構題目中。

常見陷阱

• 允許同一天買賣，卻忘了題目要求買入日必須早於賣出日。
• 在新低價出現後仍保留較高的買入價。
• 把雙層迴圈寫成 O(n)，或把固定數量變數誤判成 O(n) 空間。
• 只測上漲資料，沒有測一路下跌、相同價格和只有一天的陣列。

外部參考連結

• LeetCode 121：Best Time to Buy and Sell Stock：原始題目、範例與限制。
• TypeScript Handbook：More on Functions：函式參數與回傳型別語法。
• Node.js：assert.strictEqual()：嚴格相等 assertion 的用法。