买卖股票——从LeetCode题海中总结常见套路

这是一类很著名很经典的问题，经常在字节等面试中看见，对深入理解记忆化搜索、动态规划、状态机等技巧非常有帮助，写一篇文章来细细玩味这类问题！

目录

经典记忆化搜索：LeetCode121.买卖股票的最佳时机

两次遍历，一次找最小值，一次找最大值：

时间上进行优化：

空间上进行优化：

类似的记忆化搜索：剑指offer63.股票的最大利润

意料之外的贪心：LeetCode122.买卖股票的最佳时机II

DP状态机：LeetCode123.买卖股票的最佳时机III

状压DP：LeetCode188.买卖股票的最佳时机IV

经典记忆化搜索：LeetCode121.买卖股票的最佳时机

这是极其经典的记忆化搜索！想想什么任意一个时刻卖出股票最多的钱是多少？是当前的价格减去前面最小的那次

所以依照这个思路，定义一个数组存储前面最小的那次，然后计算出当前卖出股票所挣的钱

挣钱最多的就是最佳时机！

这里给出的依旧是一个O(n*n)的暴力思路，因为这里当前状态和往日状态息息相关，所以就为了记忆化搜索提供了切入点

具体看代码：

两次遍历，一次找最小值，一次找最大值：

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size()<=1)return 0;int minnum[prices.size()];minnum[0] = minnum[1] = prices[0];for(int i = 1;i<prices.size();i++){minnum[i] = min(minnum[i-1],prices[i-1]);}int ans = 0;for(int i = prices.size()-1;i>0;i--){if((prices[i]-minnum[i])>ans)ans = prices[i]-minnum[i];}return ans;}
};

时间上进行优化：

将两次遍历改成以此遍历：

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size()<=1)return 0;// minnum[i]表示前i个元素中最小的元素(不包括本身)int minnum[prices.size()];minnum[0] = prices[0];int ans = 0;for (int i = 1; i<prices.size(); i++) {// 记忆化搜索找出前i个元素中最小的元素minnum[i] = min(minnum[i-1], prices[i-1]);// 最大的利润等于当前的价格减去前i个元素中最小的ans = max((prices[i]-minnum[i]), ans);}return ans;}
};

空间上进行优化：

用minnum代替minnum[prices.size()]，可以降低空间复杂度

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size()<=1)return 0;// minnum表示前i个元素中最小的元素(不包括本身)int minnum = prices[0];int ans = 0;for (int i = 1; i<prices.size(); i++) {// 记忆化搜索找出前i个元素中最小的元素minnum = min(minnum, prices[i-1]);// 最大的利润等于当前的价格减去前i个元素中最小的ans = max(prices[i]-minnum, ans);}return ans;}
};

类似的记忆化搜索：剑指offer63.股票的最大利润

其实几乎是一模一样的题呀

class Solution {
public:int maxProfit(vector<int>& prices) {// 类似LeetCode121.买卖股票的最佳时机if (prices.size()<2)return 0;int minnum = prices[0];int ans = 0;for (int i = 1; i<prices.size(); i++) {minnum = min(prices[i-1], minnum);ans = max(ans, prices[i]-minnum);}return ans;}
};

意料之外的贪心：LeetCode122.买卖股票的最佳时机II

这道题确实出乎意料，表面上是前面那题改了一下，从只能买卖一次改成了可以买卖很多次

这里题目中一个关键的提示：尽可能多的完成更多的交易

这个提示就给了贪心的机会了！贪心策略：只要今天比昨天的大，就卖出，追求局部最优解，其实这就是全局最优解(不证明)

class Solution {
public:int maxProfit(vector<int>& prices) {// 贪心策略：只要今天比昨天的大，就卖出,追求局部最优解// 题目有提示：你可以尽可能地完成更多的交易（多次买卖一支股票）。int ans = 0;for (int i = 1; i<prices.size(); i++) {if ((prices[i]-prices[i-1])>0) {ans += (prices[i] - prices[i-1]);}}return ans;}
};

DP状态机：LeetCode123.买卖股票的最佳时机III

class Solution {
public:int maxProfit(vector<int>& prices) {/*对于任意一天考虑四个变量:fstBuy: 在该天第一次买入股票可获得的最大收益 fstSell: 在该天第一次卖出股票可获得的最大收益secBuy: 在该天第二次买入股票可获得的最大收益secSell: 在该天第二次卖出股票可获得的最大收益分别对四个变量进行相应的更新, 最后secSell就是最大收益值(secSell >= fstSell)*/int INF = (1<<21);int fstBuy = -INF, fstSell = 0;int secBuy = -INF, secSell = 0;for (auto p : prices) {fstBuy = max(fstBuy, -p);fstSell = max(fstSell, fstBuy + p);secBuy = max(secBuy, fstSell - p);secSell = max(secSell, secBuy + p); }return secSell;}
};

状压DP：LeetCode188.买卖股票的最佳时机IV

真TM是太难了。。。。

状压DP的坑还没填，留着后面搞吧。。。