Leetcode --- 研究经典系列问题：股票买卖问题

文章目录

121. 买卖股票的最佳时机——允许完成一次交易题目描述题目分析code 122. 买卖股票的最佳时机 II——允许多次交易题目描述题目分析code 123. 买卖股票的最佳时机 III——允许完成两次交易题目描述题目分析code 188. 买卖股票的最佳时机 IV——允许完成 $k$ 次交易题目描述题目分析code 309. 最佳买卖股票时机含冷冻期——允许多次交易并含冷冻期题目描述题目分析code 714. 买卖股票的最佳时机含手续费——允许多次交易并含手续费题目描述题目分析code

121. 买卖股票的最佳时机——允许完成一次交易

题目描述

给定一个数组，它的第 $i$ 个元素是一支给定股票第 $i$ 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。

题目分析

一次遍历寻找当前遍历过的数据的最小值，如果当前遍历到的数据不是当前遍历过的数据的最小值，那么就计算当前可以获得的最大利润。

code

class Solution { public: int maxProfit(vector<int>& prices){ int i,ans=0,minn; if(prices.empty()) return 0; //力扣的空数组奇葩数据 minn=prices[0]; //初始化 for(i=1;i<prices.size();i++){//一次遍历 if(prices[i]<minn)//判断当前遍历到的数据是否为当前遍历过的数据的最小值 minn=prices[i]; else//否则计算当前可以获得的最大利润 ans=max(ans,prices[i]-minn); } return ans;//输出 } };

122. 买卖股票的最佳时机 II——允许多次交易

题目描述

给定一个数组，它的第 $i$ 个元素是一支给定股票第 $i$ 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 提示： $1\le prices.length\le 3\times 10^4$ $0\le prices[i]\le 10^4$

题目分析

因为可以尽可能地完成更多的交易，可以多次买卖一支股票，那么说明可以用贪心。 我们逢低便买入，逢高便卖出。 只要前一天的价格小于后一天的价格便在前一天买入后一天卖出。

code

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

123. 买卖股票的最佳时机 III——允许完成两次交易

题目描述

给定一个数组，它的第 $i$ 个元素是一支给定的股票在第 $i$ 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题目分析

一道 $dp$ 题，初始化后用 $f[1]$ 存储第一次买入后可以获得的最大值，用 $f[2]$ 存储第一次买出后可以获得的最大值，用 $f[3]$ 存储第二次买入后可以获得的最大值，用 $f[4]$ 存储第二次买出后可以获得的最大值。 易得$dp$ 方程式为·： $f[1]=max(f[1],f[0]-prices[i])$ $f[2]=max(f[2],f[1]+prices[i])$ $f[3]=max(f[3],f[2]-prices[i])$ $f[4]=max(f[4],f[3]+prices[i])$

code

class Solution { public: int maxProfit(vector<int>& prices){ if(prices.empty()) return 0; int n=prices.size(); int m=max(n+1,5); int i,f[m]; f[0]=0; f[1]=-prices[0]; f[2]=INT_MIN; f[3]=INT_MIN; f[4]=INT_MIN; for(i=0;i<n;i++){ f[1]=max(f[1],f[0]-prices[i]); f[2]=max(f[2],f[1]+prices[i]); f[3]=max(f[3],f[2]-prices[i]); f[4]=max(f[4],f[3]+prices[i]); } return f[4]; } };

188. 买卖股票的最佳时机 IV——允许完成 $k$ 次交易

题目描述

给定一个整数数组 $prices$ ，它的第 $i$ 个元素 $prices[i]$ 是一支给定的股票在第 $i$ 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 $k$ 笔交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题目分析

思路与上题一致，但需要判断当 $k>=n/2$ 时的情况。 当 $k>=n/2$ 时，退化为不限制交易次数。

code

class Solution { public: int maxProfit(int k ,vector<int>& prices){ if(prices.empty()) return 0; int n=prices.size(); int i,j; if(k>=n/2){ int ans=0; for(i=1;i<n;i++) if(prices[i]>prices[i-1]) ans+=prices[i]-prices[i-1]; return ans; } int m=max(n+1,k*2+1); int f[m+1]; memset(f,0x80,sizeof(f)); f[0]=0; f[1]=-prices[0]; for(i=0;i<n;i++){ for(j=1;j<=k*2;j++){ if(j%2==1) f[j]=max(f[j],f[j-1]-prices[i]); else f[j]=max(f[j],f[j-1]+prices[i]); } } return f[k*2]; } };

309. 最佳买卖股票时机含冷冻期——允许多次交易并含冷冻期

题目描述

给定一个整数数组，其中第 $i$ 个元素代表了第 $i$ 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 $1$ 天)。

题目分析

设我们目前持有一支股票，对应的累计最大收益记为 $f[i][0]$； 我们目前不持有任何股票，并且处于冷冻期中，对应的累计最大收益记为 $f[i][1]$； 我们目前不持有任何股票，并且不处于冷冻期中，对应的累计最大收益记为 $f[i][2]$。 则易推得 $dp$ 方程式。 然后再滚动一下就好了（虽然也没省多少空间）

code

class Solution { public: int maxProfit(vector<int>& prices) { if(prices.empty()) return 0; int n=prices.size(); int f[3],x,y,z,i; memset(f,0,sizeof(f)); f[0]=-prices[0]; for(i=0;i<n;i++){ x=f[0]; y=f[1]; z=f[2]; f[0]=max(x,z-prices[i]); f[1]=x+prices[i]; f[2]=max(y,z); } return max(f[1],f[2]); } };

714. 买卖股票的最佳时机含手续费——允许多次交易并含手续费

题目描述

给定一个整数数组 $prices$，其中第 $i$ 个元素代表了第 $i$ 天的股票价格 ；非负整数 $fee$ 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

题目分析

显然是 $P2+P4$,直接放代码吧。

code

class Solution { public: int maxProfit(vector<int>& prices, int fee) { if(prices.empty()) return 0; int n=prices.size(); int i,x=0,y=-prices[0]; for(i=0;i<n;i++){ x=max(x,y+prices[i]-fee); y=max(y,x-prices[i]); } return max(x,y); } };