121. Best Time to Buy and Sell Stock（買賣股票的最佳時機）

題目描述

給定一個整數陣列 prices，其中 prices[i] 是第 i 天的股票價格。你只能選擇某一天買入，並在此後某一不同的天賣出。回傳你能獲得的最大利潤；若不能獲利，回傳 0。

原題連結：LeetCode #121 - Best Time to Buy and Sell Stock

解題思路

暴力解：雙迴圈 — O(n²)

枚舉所有買入、賣出組合，實際面試中會 TLE。

最佳解：Greedy 一次遍歷 — O(n)

維護兩個變數：

• minPrice：目前見過的最低買入價格
• maxProfit：目前最大利潤

每到新的一天，先嘗試更新 minPrice，再計算若今天賣出的利潤是否創新高。

| | 時間複雜度 | 空間複雜度 | | ------ | ---------- | ---------- | | 暴力解 | O(n²) | O(1) | | Greedy | O(n) | O(1) |

TypeScript 實作

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

  for (const price of prices) {
    if (price < minPrice) {
      minPrice = price; // 更新最低買入價
    } else if (price - minPrice > maxProfit) {
      maxProfit = price - minPrice; // 更新最大利潤
    }
  }

  return maxProfit;
}

執行步驟範例

以 prices = [7, 1, 5, 3, 6, 4] 為例：

| 天數 | 價格 | minPrice | maxProfit | 說明 | | ---- | ---- | -------- | --------- | ------------- | | 0 | 7 | 7 | 0 | 初始 minPrice | | 1 | 1 | 1 | 0 | 更新 minPrice | | 2 | 5 | 1 | 4 | 5−1=4，創新高 | | 3 | 3 | 1 | 4 | 3−1=2，未超過 | | 4 | 6 | 1 | 5 | 6−1=5，創新高 | | 5 | 4 | 1 | 5 | 4−1=3，未超過 |

最大利潤為 5（第 1 天買、第 4 天賣）

延伸思考

若可以多次買賣（LeetCode #122），則策略變成「只要明天漲就今天買」；若最多買賣 k 次（LeetCode #188），則需改用 DP。