LeetCode买卖股票问题合集

本次合集包括力扣股票买卖问题(I、II、III、IV)以及含手续费和含冷冻期。

0. 思路

对于这一类题，我们可以从状态机的角度去考虑。首先明确一点，我们不要去考虑买还是卖的问题。买股票手里的钱减少，卖股票手里的钱增加，无论什么状态，我们要保证手里的钱最多。并且，我们每一次买与卖都只与上一次的卖与买有关。

1. 我们开始！

首先我们从最简单的问题入手，买卖股票只能进行一次交易。

1.1 买卖股票的最佳时机

• 问题描述：给定一个数组prices ，它的第i个元素prices[i]表示一支给定股票第i天的价格。
• 条件：买卖一次。
• 样例：

  输入：[7,1,5,3,6,4]
  输出：5
  解释：在第2天（股票价格 = 1）的时候买入，在第5天（股票价格 = 6）的时候卖出，最大利润 = 6 - 1 = 5。
  注意利润不能是 7 - 1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

1.1.1 解决思路

我们设定两个状态，买（buy）和卖（sell），状态转移过程中保证每个状态手里的钱最多，由于最终sell状态的钱肯定是大于buy状态的，因此最后返回sell即可。

• 注意一点，buy状态是由0转移来的，因为该问题设定条件只允许买卖一次。

1.1.2 Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, sell = 0;
        for (const int & p : prices) {
            buy = max(buy, 0 - p);
            sell = max(sell, buy + p);
        }
        return sell;
    }
};

1.2 买卖股票的最佳时机 II

由于问题描述与第一题一致，就不赘述了，只是该题修改了条件，去掉了买卖一次的条件，我们可以买卖任意次。

1.2.1 解决思路

别看题目看起来棘手了一些，但是解决方法与第一题是一致的，我们同样需要设定买（buy）和卖（sell）两个状态，但由于去掉了买卖一次的条件，因此我们的buy状态直接由sell转移来即可。

1.2.2 Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, sell = 0;
        for (const int & p : prices) {
        // 注意此处 buy 状态由 sell 状态转移而来（不再是第一题的 0）
            buy = max(buy, sell - p);
            sell = max(sell, buy + p);
        }
        return sell;
    }
};

// 对于任意次的股票买卖问题，我们也可以使用贪心的方法
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 0; i < prices.size()-1; ++i)
            if (prices[i+1] > prices[i])
                res += prices[i+1] - prices[i];
        return res;
    }
};

1.3 买卖股票的最佳时机 III

股票问题III的条件变成了最多可以买卖两次。

1.3.1 解决思路

由于题目限定了最多买卖两次，那我们设定四个状态：b1, s1, b2, s2，分别代表第一次买入、卖出，第二次买入、卖出。同样的，无论是什么状态，我们都要保证其手里的钱最多。

1.3.2 Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int b1 = INT_MIN, b2 = INT_MIN;
        int s1 = 0, s2 = 0;
        for (const int & p : prices) {
            b1 = max(b1, 0 - p);
            s1 = max(s1, b1 + p);
            b2 = max(b2, s1 - p);
            s2 = max(s2, b2 + p);
        }
        return s2;
    }
};

1.4 买卖股票的最佳时机 IV

条件从第三题的最多两次改为最多k次。

1.4.1 解决思路

到了第四题，相信大家已经明白这类题的套路了，上一题因为最多买卖两次，因此我们定义了 2 * 2 个状态，那么这道题我们就定义 k * 2 个状态，但我们不必像上道题一样列出参数，只需要借助两个数组即可。同时，由于 k 可以很大，可能超过了天数的界限，因此我们可以对其进行一定的优化。

1.4.2 Code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        function<int()> greedy = [&]() {
            int res = 0;
            for (int i = 0; i < n-1; ++i)
                if (prices[i+1] > prices[i])
                    res += prices[i+1] - prices[i];
            return res;
        };
        // 如果 k 超过了最大的买卖次数上限，使用贪心算法即可
        if (k * 2 >= n) return greedy();
        vector<int> buy(k+1, INT_MIN), sell(k+1, 0);
        for (int i = 0; i < n; ++i)
            for (int j = 1; j <= k; ++j) {
                buy[j] = max(buy[j], sell[j-1] - prices[i]);
                sell[j] = max(sell[j], buy[j] + prices[i]);
            }
        return sell[k];
    }
};

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

这道题是第二题的变形，卖完要隔一天才能买。

1.5.1 解决思路

解决方式也很简单，我们只需要多设定一个冷却状态即可。即我们现在有三个状态：buy, sell_pre, sell。

1.5.2 Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, sellPre = 0, sell = 0;
        for (const int & price: prices) {
            buy = max(buy, sellPre - price);
            // 冷却期状态的上一个状态即为 sell
            sellPre = sell;
            sell = max(sell, buy + price);
        }
        return sell;
    }
};

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

每次买卖需要手续费

1.6.1 解决思路

这道题也是第二题的变形，那我们买的时候减掉手续费就可以了。

1.6.2 Code

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int buy = INT_MIN, sell = 0;
        for (const int & p : prices) {
            buy = max(buy, sell - p - fee);
            sell = max(sell, buy + p);
        }
        return sell;
    }
};

参考

• https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/5xing-dai-ma-gao-ding-suo-you-gu-piao-ma-j6zo/