跳到主要内容

买卖股票的最佳时机

问题​

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。如果不能获取利润，返回 0。

示例：

输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（价格 = 1）买入，第 5 天（价格 = 6）卖出，利润 = 6-1 = 5

输入：prices = [7,6,4,3,1]
输出：0
解释：没有交易完成，最大利润为 0

来源：LeetCode 121. 买卖股票的最佳时机

答案​

方法一：一次遍历（贪心，推荐）​

核心思路：遍历过程中维护到目前为止的最低价格，计算当前卖出的利润，取最大值。

maxProfitGreedy.ts
function maxProfit(prices: number[]): number {
  let minPrice = Infinity;  // 迄今为止的最低价
  let maxProfit = 0;        // 最大利润

  for (const price of prices) {
    if (price < minPrice) {
      // 更新最低买入价
      minPrice = price;
    } else {
      // 计算以当前价格卖出的利润
      maxProfit = Math.max(maxProfit, price - minPrice);
    }
  }

  return maxProfit;
}

执行过程演示：

prices = [7, 1, 5, 3, 6, 4]

Day 0: price=7, minPrice=7, maxProfit=0  (第一天，设为最低价)
Day 1: price=1, minPrice=1, maxProfit=0  (更低了，更新最低价)
Day 2: price=5, profit=5-1=4, maxProfit=4
Day 3: price=3, profit=3-1=2, maxProfit=4
Day 4: price=6, profit=6-1=5, maxProfit=5  ✓ 最大利润
Day 5: price=4, profit=4-1=3, maxProfit=5

结果：5
复杂度分析
  • 时间复杂度：O(n)O(n) — 一次遍历
  • 空间复杂度：O(1)O(1) — 两个变量

方法二：动态规划​

状态定义：dp[i] 表示前 i 天的最大利润。

maxProfitDP.ts
function maxProfit(prices: number[]): number {
  const n = prices.length;
  if (n < 2) return 0;

  let minPrice = prices[0];
  const dp = new Array(n).fill(0);

  for (let i = 1; i < n; i++) {
    // 前 i 天的最大利润 = max(前 i-1 天的最大利润, 第 i 天卖出的利润)
    dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
    minPrice = Math.min(minPrice, prices[i]);
  }

  return dp[n - 1];
}
与方法一的关系

方法一的贪心本质上就是空间优化后的动态规划，maxProfit 对应 dp[i]，minPrice 是维护的辅助变量。

方法三：暴力枚举（不推荐）​

枚举所有买入和卖出的组合：

maxProfitBrute.ts
function maxProfit(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(n2)O(n^2)
  • 空间复杂度：O(1)O(1)

数据规模大时会超时。

方法四：单调栈（拓展思路）​

维护一个单调递增栈，每次出栈时计算利润：

maxProfitStack.ts
function maxProfit(prices: number[]): number {
  const stack: number[] = [];
  let maxProfit = 0;

  // 在末尾添加一个 0，确保所有元素都会出栈
  prices.push(0);

  for (const price of prices) {
    while (stack.length > 0 && price < stack[stack.length - 1]) {
      const sellPrice = stack.pop()!;
      if (stack.length > 0) {
        maxProfit = Math.max(maxProfit, sellPrice - stack[0]); // 栈底是最小值
      }
    }
    stack.push(price);
  }

  prices.pop(); // 恢复原数组

  return maxProfit;
}
了解即可

单调栈解法在这道题上并不比贪心法优，但理解单调栈对后续的"接雨水"等题非常有帮助。

常见面试追问​

Q1: 如果可以多次买卖呢？(LeetCode 122)​

答案：只要第二天比第一天贵就买卖一次（贪心）：

function maxProfit(prices: number[]): number {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
}

Q2: 如果最多只能完成两笔交易呢？(LeetCode 123)​

答案：维护四个状态变量：

function maxProfit(prices: number[]): number {
  // buy1: 第一次买入后的最大收益（负数或0）
  // sell1: 第一次卖出后的最大收益
  // buy2: 第二次买入后的最大收益
  // sell2: 第二次卖出后的最大收益
  let buy1 = -Infinity, sell1 = 0;
  let buy2 = -Infinity, sell2 = 0;

  for (const price of prices) {
    buy1 = Math.max(buy1, -price);
    sell1 = Math.max(sell1, buy1 + price);
    buy2 = Math.max(buy2, sell1 - price);
    sell2 = Math.max(sell2, buy2 + price);
  }

  return sell2;
}

Q3: 如果有冷冻期（卖出后隔一天才能买）呢？(LeetCode 309)​

答案：

function maxProfit(prices: number[]): number {
  const n = prices.length;
  if (n < 2) return 0;

  // hold: 持有股票的最大收益
  // sold: 刚卖出（冷冻期）的最大收益
  // rest: 不持有股票且不在冷冻期
  let hold = -prices[0];
  let sold = 0;
  let rest = 0;

  for (let i = 1; i < n; i++) {
    const prevHold = hold;
    hold = Math.max(hold, rest - prices[i]); // 买入
    rest = Math.max(rest, sold);              // 冷冻期结束
    sold = prevHold + prices[i];              // 卖出
  }

  return Math.max(sold, rest);
}

Q4: 为什么贪心法是正确的？​

答案：

因为我们要找最大差值 prices[j] - prices[i]（j > i），这等价于：

  • 维护 i 之前的最小值 minPrice
  • 对于每个 j，用 prices[j] - minPrice 更新答案

这样一次遍历就能保证：每个位置 j 都和它前面所有日子中最便宜的那天做了比较。

相关链接​