121.买卖股票的最佳时机

LeetCode 原题链接 题目

动态规划

dp 数组含义

题目要求最多只完成一笔交易，也就是只能买入一次、卖出一次。

每天结束后，手里只有两种状态：

dp[i][0] // 第 i 天结束后，不持有股票时的最大利润
dp[i][1] // 第 i 天结束后，持有股票时的最大利润

这里的“第 i 天结束后”表示当天的操作已经考虑完了。当天可以选择买入、卖出，或者什么都不做。

最终答案应该是不持有股票的最大利润，也就是：

dp[prices.length - 1][0]

如果最后还持有股票，说明只买了没有卖，利润不会是最终答案。

确定状态转移方程

第 i 天结束后不持有股票

dp[i][0] 有两种来源：

  1. 昨天就不持有股票，今天什么都不做：
dp[i - 1][0]
  1. 昨天持有股票，今天卖出：
dp[i - 1][1] + prices[i]

所以：

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

第 i 天结束后持有股票

dp[i][1] 也有两种来源：

  1. 昨天就持有股票，今天继续持有：
dp[i - 1][1]
  1. 今天第一次买入股票：
-prices[i]

本题最多只能完成一笔交易，所以买入之前的利润只能是 0，不能写成 dp[i - 1][0] - prices[i]。如果那样写，就表示可以把之前卖出的利润继续拿来买第二次股票了。

所以：

dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);

dp 数组如何初始化

第 0 天只有一个价格 prices[0]。

dp[0][0] = 0;
dp[0][1] = -prices[0];

含义：

  • dp[0][0] = 0：第 0 天结束后不持有股票，说明什么都没做，利润是 0。
  • dp[0][1] = -prices[0]：第 0 天结束后持有股票，说明在第 0 天买入了股票，利润是负的买入价格。

如果 prices 为空，没有任何交易可以做，直接返回 0。

确定遍历顺序

dp[i][0] 依赖：

dp[i - 1][0]
dp[i - 1][1]

dp[i][1] 依赖：

dp[i - 1][1]

当前第 i 天的状态都依赖前一天的状态，所以遍历顺序是从前往后：

for (let i = 1; i < prices.length; i++) {
  // 更新 dp[i][0] 和 dp[i][1]
}

举例推导

以 prices = [7, 1, 5, 3, 6, 4] 为例。

初始化：

第 0 天，价格 7
dp[0] = [0, -7]

完整 dp 数组变化如下：

下标 i     价格     dp[i][0] 不持股     dp[i][1] 持股
0          7        0                  -7
1          1        0                  -1
2          5        4                  -1
3          3        4                  -1
4          6        5                  -1
5          4        5                  -1

解释几个关键位置：

  • 第 1 天价格为 1，此时买入更便宜，所以 dp[1][1] = -1。
  • 第 2 天价格为 5，如果卖出，利润是 5 - 1 = 4，所以 dp[2][0] = 4。
  • 第 4 天价格为 6，如果卖出，利润是 6 - 1 = 5，所以 dp[4][0] = 5。

最终答案：

dp[5][0] = 5

也就是在价格为 1 时买入，价格为 6 时卖出，最大利润为 5。

代码实现

var maxProfit = function (prices) {
  if (prices.length === 0) return 0;

  const dp = new Array(prices.length).fill(0).map(() => [0, 0]);

  dp[0][0] = 0;
  dp[0][1] = -prices[0];

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

  return dp[prices.length - 1][0];
};

复杂度分析

  • 时间复杂度：O(n)，只遍历一次价格数组。
  • 空间复杂度：O(n)，使用 dp 数组保存每天的两个状态。

空间优化

因为第 i 天只依赖第 i - 1 天，所以可以用两个变量代替整个 dp 数组。

var maxProfit = function (prices) {
  if (prices.length === 0) return 0;

  let noStock = 0;
  let hasStock = -prices[0];

  for (let i = 1; i < prices.length; i++) {
    noStock = Math.max(noStock, hasStock + prices[i]);
    hasStock = Math.max(hasStock, -prices[i]);
  }

  return noStock;
};

贪心算法

解题思路

要想在第 i 天卖出股票并获得尽可能多的利润，买入价格应该是第 0 天到第 i - 1 天之间的最低价格。

因此遍历价格数组时，只需要维护两个变量：

minPrice // 当前遍历过的最低价格
maxProfit // 当前能够获得的最大利润

对于每天的价格 prices[i]：

  1. 假设今天卖出，利润为 prices[i] - minPrice，用它更新最大利润。
  2. 用今天的价格更新最低买入价格，为后面的卖出做准备。

每一天都选择此前最低的价格作为买入点，这是当前卖出日期下的最优选择；遍历所有可能的卖出日期后，就能得到全局最大利润。

举例推导

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

价格     当前最低价     当天卖出利润     最大利润
7        7              0                0
1        1              0                0
5        1              4                4
3        1              2                4
6        1              5                5
4        1              3                5

最终最大利润为 5。

代码实现

var maxProfit = function (prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

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

  return maxProfit;
};

复杂度分析

  • 时间复杂度：O(n)，只遍历一次价格数组。
  • 空间复杂度：O(1)，只使用两个变量。