algorithms►leetcode

033-买卖股票的最佳时机(贪心)

122. 买卖股票的最佳时机 II

问题描述

给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。你可以多次买卖这支股票，但必须在再次购买前卖出之前的股票。计算你能获得的最大利润。

示例

1
2
3
4
5
6
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 
- 第2天买入（1），第3天卖出（5），利润 = 5-1 = 4
- 第4天买入（3），第5天卖出（6），利润 = 6-3 = 3
总利润 = 4 + 3 = 7

方法一：贪心算法

核心思想

  • 只要今天的价格比昨天高，就进行交易（昨天买入，今天卖出）。
  • 因为可以多次交易，所有正利润的累加就是最大利润。

代码

1
2
3
4
5
6
7
8
9
var maxProfit = function(prices) {
    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;
};

复杂度分析

  • 时间复杂度：O(n)，只需遍历一次数组。
  • 空间复杂度：O(1)，仅用常数空间。

方法二：动态规划

核心思想

  • 状态定义：
    • dp[i][0]：第 i 天结束时未持有股票的最大利润。
    • dp[i][1]：第 i 天结束时持有股票的最大利润。
  • 状态转移：
    • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
      （前一天未持有，或前一天持有今天卖出）
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
      （前一天持有，或前一天未持有今天买入）

代码

1
2
3
4
5
6
7
8
9
10
11
12
var maxProfit = function(prices) {
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => [0, 0]);
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    
    for (let i = 1; i < n; 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], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
};

优化空间

1
2
3
4
5
6
7
8
9
10
var maxProfit = function(prices) {
    let [hold, notHold] = [-prices[0], 0];
    for (const p of prices) {
        [hold, notHold] = [
            Math.max(hold, notHold - p),
            Math.max(notHold, hold + p)
        ];
    }
    return notHold;
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)（优化后）。

方法对比

方法 时间复杂度 空间复杂度 适用场景
贪心 O(n) O(1) 简单高效，直接累加利润
动态规划 O(n) O(n) 或 O(1) 通用性强，可扩展性高

关键点总结

  1. 贪心算法：
    • 核心是 “所有正利润之和”，适用于本题的无限次交易。
  2. 动态规划：
    • 通过状态转移方程覆盖所有可能操作，适合更复杂的股票问题（如含手续费、冷冻期等）。

最终推荐

  • 直接使用贪心算法（代码简洁，效率高）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    var maxProfit = function(prices) {
        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;
    };