买卖股票最佳时机

[!abstract] 问题 只能交易一次（买一次，卖一次），求最大利润。

示例

输入: prices = [7,1,5,3,6,4]
输出: 5
解释: 第2天买入(1)，第5天卖出(6)，利润=5

输入: prices = [7,6,4,3,1]
输出: 0
解释: 没有有利交易

解法

方法1: 一次遍历 O(n)

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

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

方法2: DP

function maxProfitDP(prices: number[]): number {
  let dp0 = 0;           // 不持有股票的最大利润
  let dp1 = -Infinity;   // 持有股票的最大利润

  for (const price of prices) {
    dp0 = Math.max(dp0, dp1 + price);  // 卖出
    dp1 = Math.max(dp1, -price);        // 买入
  }

  return dp0;
}

方法3: 暴力 O(n²)

function maxProfitBrute(prices: number[]): number {
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      max = Math.max(max, prices[j] - prices[i]);
    }
  }
  return max;
}

复杂度

方法	时间	空间
一次遍历	O(n)	O(1)
DP	O(n)	O(1)
暴力	O(n²)	O(1)

核心思想

遍历过程中记录最小价格
最大利润 = max(历史最大利润, 当前价格 - 最小价格)

---

参见: **股票问题** | **买卖股票最佳时机II**