总结一下力扣上的股票交易问题。有：

1. 121.买卖股票的最佳时机

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

3. 123. 买卖股票的最佳时机 III

4. 188. 买卖股票的最佳时机 IV

5. 309. 最佳买卖股票时机含冷冻期

6. 714. 买卖股票的最佳时机含手续费

这些问题基本上都是差不多的套路，都可以使用动态规划或是贪心解决。

121.买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

题目简述：给定一个数组表示第 i 天的股票价格，规定最多只能完成一笔交易（买入+卖出一次），求能获取的最大利润。

例1：

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

例2：

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解法1：

  由于规定了只能买卖一次，因此我们要想得到最大利润，那么我们肯定是要在最低价格的时候买入，在最高价格的时候卖出。并且我们不能在买入前卖出，也就是我们要找到在买入之后的最高价格。

  按照这个想法，代码是这样的：

var maxProfit = function(prices) {
    let len = prices.length;
    let maxPro = 0;
    // 首先初始化第一天的最低最高价
    let min = prices[0], max = prices[0];

    for (let i = 1; i < len; i++) {
        // 若找到了一个更低的价格，那么重置最高最低价
        if (min > prices[i]) {
            min = max = prices[i];
        }
		// 找到买入价格之后的最高价
        max = Math.max(max, prices[i]);
        // 对每个较高的价格进行一次计算
        maxPro = Math.max(maxPro, max - min);
    }

    return maxPro;
};

  上面的代码可以再简化，最高价 max 其实是不必要的，因为我们 max 每次循环都会更新为较大值，并且这个较大值我们只需要用到一次，后面当 max 没变化时， maxPro 的计算就重复了。

  因此我们只需要更新 min 的价格，max 使用每天的价格 prices[i] 替代即可：

var maxProfit = function(prices) {
    let len = prices.length;
    let maxPro = 0;
    let min = prices[0];

    for (let i = 1; i < len; i++) {
        min = Math.min(min, prices[i]);
        // 计算当天价格与历史最低价的差，选取最高利润
        maxPro = Math.max(maxPro, prices[i] - min);
    }

    return maxPro;
};

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

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

题意简述：给定数组 prices，第 i个元素是股票第 i 天的价格。

规定可以完成多次交易，但手中最多只能持有一只股票（即在卖出之前不能买入）。

例1：

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

例2：

输入: [1,2,3,4,5]

输出: 4

解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

解法1：贪心1

  我们可以把股票的价格看作一张折线图：

  想要获取多次交易的最大利润，其实就是找到折线图中的波峰波谷位置，我们每次买入股票时贪心的选择距离我们最近的波谷点买入，然后再选择最近的波峰处卖出。如上图就是先选择第二天的波谷 1 买入，再选择第三天的波峰 5 卖出；再选择第四天的波谷 3 买入，再选择第五天的波峰 6 卖出。

  这样下来获得的利润就是：(5 - 1) + (6 - 3) = 7

  再注意边界的处理即可：

var maxProfit = function(prices) {
    let profit = 0;
    let len = prices.length;
    let cost; // 当前持有的股票价格
    let i = 0;

    while(i < len) {
        // 先找到波谷
        while(i + 1 < len && prices[i] > prices[i+1]) {
            i++;
        }
        cost = prices[i++];
		
        // 边界处理
        if (i < len) {
            // 再找到波峰
            while(i + 1 < len && prices[i] < prices[i+1]) {
                i++;
            }
            profit += prices[i++] - cost;
        }
    }

    return profit;
};

解法2：贪心2

  我们观察一下 例2 的折线图：

  我们知道它的最大利润是在第一天买入，在第五天卖出，也就是 5 - 1 = 4，这和我们连续交易四次获得的利润是一样的：(2 - 1) + (3 - 2) + (4 - 3) + (5 - 4) = 4。

  因此我们可以一天天的累积，当上一天的价格比当天价格低时，我们的最终利润就加上这个差价，否则就不用管它。

var maxProfit = function(prices) {
    let len = prices.length;
    let profit = 0;

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

    return profit;
};

解法3：动态规划

  对于股票交易，我们只有两种状态：未持有股票 和 持有股票。

  因此我们可以使用一个数组来存储每一天在每个状态下能够获取的最大利润：dp[len][2]。

  其中 dp[i][0] 表示第 i 天未持有股票所能够获得的最大利润

  dp[i][1] 表示第 i 天持有股票能够获得的最大利润。

  因此，对于第 i 天：

• 未持有股票能够获得的最大利润也可以从第 i-1 天的状态转移而来，也就是：

  • 第 i-1 天持有股票，在第 i 天卖出：dp[i-1][1] + prices[i]
  • 第 i-1 天未持有股票，第 i 天也没有买入：dp[i-1][0]

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

• 持有股票能够获得的最大利润可以从第 i-1 天的状态转移而来，也就是：

  • 第 i-1 天未持有股票，在第 i 天买入了股票：dp[i-1][0] - prices[i]
  • 第 i-1 天就已经持有了股票：dp[i-1][1]

  也就是 dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])

  边界也就是第 1 天持有股票的话，最大利润 dp[0][1] = -prices[0] （买入花了这么多钱）

  其他默认为 0，表示还未获得利润。

  最后返回最后一天未持有股票的最大利润，因为我们不可能在最后一天还花钱买股票，后面就没得卖了…

var maxProfit = function(prices) {
    let n = prices.length;
    let dp = new Array(n).fill(0).map(() => new Array(2).fill(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];
};

空间优化

  仔细观察可以发现，我们第 i 天的状态都只由第 i-1 天的状态转移而来，那么第 0 - i-2 天的状态就都没用了，因此我们可以节约空间，只使用两个变量保存上一天的状态即可。

  具体我们使用 hold 表示持有股票能获取的最大利润；

  使用 unhold 表示未持有股票能获取的最大利润。

  根据我们上面的分析：

  hold 能由 unhold 转移而来：hold = max(hold, unhold - prices[i]) （上一天未持有，当天买入）

  unhold 也能由 hold 转移而来：unhold = max(unhold, hold + prices[i]) （上一天持有，当天卖出）

  同样，初始化第一天持有股票的状态 hold = -prices[0]，未持有股票的状态 unhold = 0、

  在下面的代码中，我们在同一天中更新了 hold 和 unhold 这两个状态，按我们对这两个变量的定义，它们在未更新前是表示上一天状态，但我们在更新时却使用了当天更新后的其中一个状态来更新另一个状态，这样不是会有影响吗？

  乍一看感觉会有影响，不过我们再进一步分析可以发现，这其实是没有影响的，为了方便观察，我们把上一天的状态定义为 hold1和 unhold1，当天的状态定义为 hold 和 unhold：

  我们在代码中先更新了 hold 状态为 hold = max(hold1, unhold1 - prices[i])

  然后我们更新 unhold ：unhold = max(unhold1, hold1 + prices[i])

  更新后的 hold 由上一天的 hold1 和上一天的 unhold1 - prices[i] 决定的。

  我们将这两个因素带入表达式中：unhold = max(unhold1, hold1 + prices[i], unhold1 - prices[i] + prices[i])。

  其实就是等于 unhold = max(unhold1, hold1 + prices[i], unhold1)，对我们的状态更新并没有影响！

var maxProfit = function(prices) {
    let n = prices.length;
    let hold = -prices[0];
    let unhold = 0;

    for (let i = 1; i < n; ++i) {
        hold = Math.max(hold, unhold - prices[i]);
        unhold = Math.max(unhold, hold + prices[i]);
    }

    return unhold;
};

123. 买卖股票的最佳时机 III

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

题意简述：给定一个数组 prices ，它的第 i 个元素是股票在第 i 天的价格。

限制最多只能完成两笔交易，且手中最多只能同时持有一只股票。

例1

输入：prices = [3,3,5,0,0,3,1,4]

输出：6

解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

解法1：动态规划

  这题和 121.买卖股票的最佳时机 非常相似，区别就是 121. 规定只能买卖一次，而本题最多能买卖两次。

  我们 121. 中的想法是：遍历 prices 数组，在遍历过程中，我们不断更新最低价格，并使用这个最低价格和每天的股票价格 prices[i] 来更新我们的最高利润（max(profit, prices[i] - min)）。

  而本题可以交易两次，那这样，我们可以沿袭 121. 中的思路，不断记录第一次交易完后最大的利润 profit1， 视其为我们第一次交易完后赚的钱，然后再使用相同的思路计算第二次交易能得到的最大利润。

  也就是在完成第一笔交易后，我们继续寻找一个最低的价格来让我们买完第二支股票后手里剩下的钱最多（left = max(left, profit1 - prices[i])），然后再使用每天的 prices[i] 不断更新我们售出第二只股票能获取的最大利润：profit2 = max(profit2, left + prices[i])。

  有的情况下，我们只需要交易一次即可得到最高利润，不过上面的状态转移其实也包括了这种情况：即我们的 profit1 其实就是最终结果（最高的利润），这种情况下，我们的 left = profit1 - prices[i]，然后我们使用它来计算出profit2： profit2 = max(profit2, profit1 - prices[i] + prices[1])，也就是 profit2 = profit1。因此也会得到正确结果。

var maxProfit = function(prices) {
    let n = prices.length;

    let min = prices[0], profit1 = 0;
    let left = -Number.MAX_VALUE, profit2 = 0;

    for (let i = 1; i < n; ++i) {
        let p = prices[i];
        // 不断更新第一次买卖的最低股票价格
        min = Math.min(min, p);
        // 不断更新第一次买卖后获得的最高利润
        profit1 = Math.max(profit1, p - min);

        // 第二次买入股票后我们手中还剩下的钱
        left = Math.max(left, profit1 - p);
        // 第二次卖出股票后我们能获取的最高利润
        profit2 = Math.max(profit2, left + p);
    }

    return profit2;
};

188. 买卖股票的最佳时机 IV

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

题意简述：给定一个数组 prices ，它的第 i 个元素是股票在第 i 天的价格。

限制最多只能完成 k 笔交易，且手中最多只能同时持有一只股票。

例 2：

输入：k=2, prices = [3,2,6,5,0,3]

输出：7

解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

解法1：动态规划

  这题是 123. 买卖股票的最佳时机 III 的拓展，123. 中限制了最多买卖两次，而本题最多买卖次数不定。

  123. 中使用了两组变量来分别保存第一次交易和第二次交易的最低开销和最高利润。那么本题我们就使用 k 组变量来保存这两个状态即可。

  沿袭 123. 中的动态规划思想，我们很容易就能写出答案：

var maxProfit = function(k, prices) {
    if (k === 0) {
        return 0;
    }
    let n = prices.length;
	
    // hold 表示买入当前股票需要的最低开销
    let hold = new Array(k).fill(-Number.MAX_VALUE);
    // unhold 表示未持有股票所能得到的最高利润，这个利润可能是当天卖出股票得到的，也可能是前面的交易得到的最高利润。
    let unhold = new Array(k).fill(0);
    hold[0] = prices[0];

    for (let i = 1; i < n; i++) {
        let p = prices[i];
        hold[0] = Math.min(hold[0], p);
        unhold[0] = Math.max(unhold[0], p - hold[0]);
        for (let j = 1; j < k; j++) {
            hold[j] = Math.max(hold[j], unhold[j-1] - p);
            unhold[j] = Math.max(unhold[j], hold[j] + p);
        }
    }

    return unhold[k-1];
};

309. 最佳买卖股票时机含冷冻期

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

题意简述：给定一个数组 prices ，它的第 i 个元素是股票在第 i 天的价格。

约束条件：

• 卖出股票后无法在第二天买入股票（冷冻期为 1 天）
• 手中只能同时持有一只股票

求在任意交易次数后能够获得的最大利润。

示例:

输入: [1,2,3,0,2]

输出: 3

解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解法1：动态规划

  前面几题的交易状态只有两种：持有股票 和 未持有股票，而本题多了一种状态：处于冷冻期。

  因为有了前面几题的经验，我们可以知道，这些状态其实都是由上一次的状态转移而来，因此我们只需要设置三个变量来代表这三个状态即可。

我们设置

• hold 表示当天交易过后持有股票的状态下能够获得的最大利润
• unhold 表示当天交易过后未持有股票的状态下能够获得的最大利润
• freeze 表示当前交易过后处于冷冻期的状态下能够获得的最大利润

  因此 hold 的状态能够由 hold（仍然保持持有股票的状态）和 unhold （当天新买入股票，从未持有股票转移到持有股票）转移而来，也就是：hold = max(hold, unhold - prices[i])

  unhold 状态能够由 unhold（仍然保持未持有股票状态）和 freeze（刚从冷冻期恢复）转移而来，也就是：unhold = max(unhold, freeze)

  而 freeze 状态只能由 hold 状态转移而来（将持有的股票卖出，进入冷冻期），并不能由 freeze 转移，因为冷冻期只有一天！因此 freeze = hold + prices[i]。

  状态初始化：hold = -prices[0]，unhold = freeze = 0

var maxProfit = function(prices) {
    let n = prices.length;

    let hold = -prices[0], unhold = 0, freeze = 0;

    for (let i = 1; i < n; i++) {
        hold = Math.max(hold, unhold - prices[i]);
        unhold = Math.max(unhold, freeze);
        freeze = hold + prices[i];
    }

    return Math.max(freeze, unhold);
};

714. 买卖股票的最佳时机含手续费

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

题意简述：给定 prices 数组，数组元素 i 表示股票第 i 天的价格。

可以进行尽可能多次交易，不过手中最多只能持有一只股票，且每次交易（一次买入卖出）都需要支付手续费 fee，求股票交易的最大利润。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2

输出: 8

解释: 能够达到的最大利润:

在此处买入 prices[0] = 1

在此处卖出 prices[3] = 8

在此处买入 prices[4] = 4

在此处卖出 prices[5] = 9

总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

解法1：贪心

  我们可以将手续费算在股票的价格中，也就是每次买入股票需要花费 prices[i] + fee，这样，我们遍历 prices 数组，且不断更新购买股票的最小花费 cost，在遍历过程中，若将手中最小花费的股票cost 以当天价格 prices[i] 卖出我们能获利的话（prices[i] > cost），那么我们就选择将其卖出 : profit += prices[i] - cost 并重置最小花费 cost 为当天的价格：cost = prices[i]，因为我们已经不能再以之前的价格买入股票了。

var maxProfit = function(prices, fee) {
    let profit = 0;
    let len = prices.length;
    let cost = Number.MAX_VALUE;

    for (let p of prices) {
        cost = Math.min(p + fee, cost);
        if (p > cost) {
            profit += p - cost;
            cost = p;
        }
    }

    return profit;
};

解法2：动态规划

  动态规划方法还是老样子，股票交易有两个状态：持有股票 hold 和未持有股票 unhold。且我们的股票交易状态只与前一次的交易状态有关。

  持有股票状态能够由未持有股票状态转移而来：hold = max(hold, unhold - prices[i])；

  未持有股票状态能够由持有股票状态转移而来：unhold = max(unhold, hold + prices[i])。

代码如下：

var maxProfit = function(prices, fee) {
    let n = prices.length;
    let hold = -prices[0], unhold = 0;

    for (let i = 1; i < n; ++i) {
        hold = Math.max(hold, unhold - prices[i]);
        unhold = Math.max(unhold, hold + prices[i] - fee);
    }

    return unhold;
};

股票问题小结

  连续写了六道股票问题，对这类问题的解题思路清晰了很多。

  对于股票问题，动态规划基本是通用的，即先确定股票的状态（持有、未持有、冷冻期），然后再确定这些状态之间的转移关系，一般是：

• 持有 hold 状态可由未持有转移而来：hold = max(hold, unhold - prices[i])（未持有状态下的利润减去当天买入股票的开销）
• 未持有 unhold 状态可由持有状态转移而来：unhold = max(unhold, hold + prices[i]) （持有股票状态下的利润加上当天卖出股票所能获得的利润）

  边界则是第一天的状态：hold = -prices[0]，unhold = 0

  有些问题可以使用贪心思路解决：即我们只进行那些能让我们获得利润的交易（买入价格低于卖出价格）。我们遍历 prices 数组，不断更新我们最低的买入价格 cost，当 prices[i] 大于 cost 时，我们能够获利，此时可以选择将其卖出。

  有些情况下，题目有限制条件，即我们最多只能完成 k 次交易。

• 若最多只能完成一次交易，那么我们可以在更新最低买入价格 cost 的过程中，不断计算我们的最高利润 max(profit, prices[i] - cost)。
• 若最多完成交易次数大于一次，那么我们第 i 次交易能够获得的利润需要由第 i-1 次交易能获得的利润转移而来（动态规划），这种情况下，我们视第 i-1 次交易所能获得的利润为我们的本金，我们可以选择是否要买入当前股票：max(不买入，买入) ： max(cost[i], profit[i-1] - prices[i])，并以第 i 次交易的本金来计算是否能够得到更高的利润：max(profit[i], cost[i] + prices[i])。