文章目录
- 题目链接:
- 题目描述:
- 解题思路一(贪心算法):
- 解体思路二(动态规划):
题目链接:
122.买卖股票的最佳时机II
题目描述:
解题思路一(贪心算法):
本问题可以通过贪心算法解决。我们可以将问题分解为一系列连续的上涨子序列,并在每个上涨子序列中,计算利润,并将其累加到最终的结果中。具体的做法是:
- 贪心算法的核心思想:对于每个上升的子序列,我们希望在价格上涨时不断买入,价格下跌时卖出。
- 连续上升子序列:在遍历股票价格的过程中,如果当前价格小于下一天的价格,说明价格在上涨,应该继续持有股票;如果当前价格大于或等于下一天的价格,说明我们已经遇到了一个下降的趋势,在此时卖出,计算当前区间的利润。
- 利润计算:每次找到一个上涨子序列时,我们就将该子序列的利润(即当前价格减去子序列的起始价格)累加到总利润中。
复杂度分析:
时间复杂度O(N)
空间复杂度O(1)
代码实现方式一:
找到每一个连续递增子序列,将其差值作为利润记录到总利润中
class Solution {
public:int maxProfit(vector<int>& prices) {int p1 = 0;int p2 = 0;int res = 0;int n = prices.size();while(p2<n-1){if(prices[p2]< prices[p2+1]){p2++;continue;}else{res = res + (prices[p2]-prices[p1]);p2++;p1=p2;}}return res+(prices[p2]-prices[p1]);}
};
代码实现方式2:
- 每次遍历数组,比较相邻的价格(即
prices[i]
和prices[i+1]
): - 如果
prices[i+1] > prices[i]
,则说明价格上涨,可以在今天买入,明天卖出,获得的利润是prices[i+1] - prices[i]
。 - 如果
prices[i+1] <= prices[i]
,则不进行操作,不获得任何利润。
利用max(0, prices[i+1] - prices[i])
确保当价格下降时不加入负的利润。 - 本质上与第一种方式一致,但是这种实现方式更简洁
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int res = 0;for(int i=0; i<n-1; i++){res += max(0, prices[i+1]-prices[i]);}return res;}
};
解体思路二(动态规划):
由于题目中要求在任何时候手里最多只有一支股票,因此在每天交易完成后,只可能手里有一支股票或者没有股票的状态
我们可以定义:
dp[i][0]
: 表示第i天交易完成后手里没有股票的最大利润(i从0开始)dp[i][1]
: 表示第i天交易完成后手里持有一支股票的最大利润(i从0开始)
因此dp[i][0]
的转移方程,如果这一天交易完成后手里没有股票,那么可能的状态转移为前一天已经没有股票了,即 dp[i-1][0]
,或者前一天结束的时候手里有一支股票,即dp[i-1][1]
,这时候我们要将其卖出,并获得prices[i]收益。因此为了利益最大化,我们的状态转移方程:
d p [ i ] [ 0 ] = max ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ i ] ) dp[i][0] = \max \left( dp[i-1][0], dp[i-1][1] + prices[i] \right) dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])
再来考虑dp[i][1]
,如果转移状态前一天已经持有一支股票。即dp[i-1][1]
,或者前一天结束的时候手里没有股票,即dp[i-1][0]
,这时候我们要将其买入,并减少prices[i]
的收益。可以列出状态转移方程:
d p [ i ] [ 1 ] = max ( d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] , d p [ i − 1 ] [ 1 ] ) dp[i][1] = \max \left( dp[i-1][0] - prices[i], dp[i-1][1] \right) dp[i][1]=max(dp[i−1][0]−prices[i],dp[i−1][1])
对于初始状态,我们直到在第0天交易结束的时候:
dp[0][0] = 0
dp[0][1] = -prices[0]
代码实现:
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int dp[n][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i=1; i<n; i++){dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);}return dp[n-1][0];}
};
动态规划解析参考:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/476791/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/?envType=study-plan-v2&envId=top-interview-150