LeetCode刷题笔记 121 122 123 188股票买卖系列通用解法

84 阅读 0 评论 56 点赞

我是靠谱客的博主踏实香菇，这篇文章主要介绍LeetCode刷题笔记 121 122 123 188股票买卖系列通用解法，现在分享给大家，希望可以做个参考。

题目：买卖股票的最佳时机I

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

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

示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

答案：
两个指针，分别指向买入和卖出的位置。买入初始化为第一天，卖出初始化为第二天，在卖出滑动到最后一天的过程中：如果卖出位置的价格小于当前买入位置的价格，则选择在卖出位置处买入，在滑动过程中一直更新最大收益（卖出-买入）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) return 0;
int buy = 0;
int sell = 1;
int max = 0;
while(sell < prices.length) {
if(prices[sell] < prices[buy])
buy = sell;
//更新最小价格位置
else max = Math.max(max,prices[sell]-prices[buy]);
//更新最大收益
sell++;
}
return max;
}
}

时间复杂度：O(n)，只需要遍历一次。
空间复杂度：O(1)，只使用了三个变量。

讨论区的优质想法：
假设当前在第 i 天，令 minPrice 表示前 i-1 天的最低价格；令 maxProfit 表示前 i-1 天的最大收益。那么考虑第 i 天的收益时，存在两种情况：
（1）在第 i 天卖出。很显然，想要获得最大收益，应该在前 i-1 天中价格最低的时候买入，即此时的收益为：prices[i] - minPrice。（可能会出现负数，但是没关系）
（2）不在第 i 天卖出。那么第 i 天的最大收益就等于前 i -1 天中的最大收益
状态转移方程为：第 i 天最大收益 = max( 在第 i 天卖出的所得收益 , 前 i-1 天的最大收益)

复制代码

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
minPrice = Math.min(minPrice, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}

时间复杂度：O(n)，只需要遍历一次。
空间复杂度：O(1)，只使用了两个变量。

题目：买卖股票的最佳时机II

给定一个数组，它的第 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 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

答案：
贪心算法：遍历整个股票交易日价格列表 price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。（因为可以不限制次数的买卖）
（1）设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1] ；
（2）当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为 0 或为负，则直接跳过；
（3）遍历完成后，返回总利润 profit。

复制代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
int tmp = prices[i] - prices[i - 1];
if (tmp > 0) profit += tmp;
}
return profit;
}
}

时间复杂度：O(n)，只需要遍历一次。
空间复杂度：O(1)，只使用了两个变量。

题目：买卖股票的最佳时机III

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

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

答案：

动态规划

参考链接：https://blog.csdn.net/qq_41231926/article/details/84451773

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int maxProfit(int[] prices) {
int buy1 = Integer.MAX_VALUE;
int sell1 = 0;
int buy2 = Integer.MAX_VALUE;
int sell2 = 0;
for(int i = 0; i < prices.length; i++){
sell1 = Math.max(sell1, prices[i] - buy1);
//在第i天完成第一次卖出的最大收益值
buy1 = Math.min(buy1, prices[i]);
//第一次最小买入价格
sell2 = Math.max(sell2, prices[i] - buy2);
//在第i天完成第二次卖出的总最大收益值（连同第一次一起）
buy2 = Math.min(buy2, prices[i] - sell1);
//第二次最小买入价格（连同第一次一起）
}
return sell2;
}
}

时间复杂度：O(n)
空间复杂度：O(1)

注：对第二次买入及卖出的价格的理解：
以数组[7,1,5,3,6,4]为例，第1天完成第一次买入，价格为1，第2天完成第一次卖出，收益为5-1=4，第3天完成第2次买入，价格为3-(5-1)=-1，即因为第一次卖出收益了4元，现在花出去3元，相当于以-1元的价格买入，第4天完成第2次卖出，总最大收益为6-(-1)=7。
即第二次卖出获得的两次交易的总收益只与第二次买入价格（等效价格）有关，第二次买入价格与第一次卖出的收益有关。

股票买卖系列通用解法

参考链接：
动态规划之股票买卖系列共6题
一个通用方法团灭6道股票问题

思路一:

首先考虑影响状态的变量：
当前处于第几天；
已经交易的次数；
手头是否持有股票；
即根据手头是否持有股票，我们定义两个二维数组来定义状态：

复制代码

1
2
3
dp0[i][j]: 第i天结束，已有j次买卖，手头没有股票时的最大利润
dp1[i][j]: 第i天结束，已有j次买卖，手头有股票时的最大利润

先看初始状态:

复制代码

1
2
3
当i==0 && j>=0: dp0[0][j] = 0, dp1[0][j] = -prices[0];
当i>0 && j==0: dp0[i][0] = 0, dp1[i][0] = max(dp1[i-1][0], -prices[i]);

再来考虑状态转移方程，当i>0且j>0时有

复制代码

1
2
3
dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j-1] + prices[i]) # 保持 or 卖出
dp1[i][j] = max(dp1[i-1][j], dp0[i-1][j] - prices[i]) # 保持 or 买入

具体分析

1.买卖一次

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int[][] dp0 = new int[len][2];
int[][] dp1 = new int[len][2];
dp1[0][0] = -prices[0];
for(int i = 1; i < len; i++) {
dp1[i][0] = Math.max(dp1[i-1][0],-prices[i]);
//j = 0
dp0[i][1] = Math.max(dp0[i-1][1],dp1[i-1][0]+prices[i]); // 保持 or 卖出
}
return dp0[len-1][1];
}
}

空间复杂度优化

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int[] dp0 = new int[2];
int[] dp1 = new int[2];
dp1[0] = -prices[0];
for(int i = 1; i < len; i++) {
int tmp = dp1[0];
dp1[0] = Math.max(dp1[0],-prices[i]);
//j = 0
dp0[1] = Math.max(dp0[1],tmp+prices[i]); // 保持 or 卖出
}
return dp0[1];
}
}

2.不限买卖次数

dp0[i]: 第i天结束，手头没有股票时的最大利润
dp1[i]: 第i天结束，手头有股票时的最大利润

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int[] dp0 = new int[len];
int[] dp1 = new int[len];
dp1[0] = -prices[0];
for(int i = 1; i < len; i++) {
dp0[i] = Math.max(dp0[i-1],dp1[i-1]+prices[i]); // 保持 or 卖出
dp1[i] = Math.max(dp1[i-1],dp0[i-1]-prices[i]); // 保持 or 买入
}
return dp0[len-1];
}
}

3.买卖两次

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int[][] dp0 = new int[len][3];
int[][] dp1 = new int[len][3];
dp1[0][0] = -prices[0]; dp1[0][1] = -prices[0]; // i = 0
for(int i = 1; i < len; i++) {
dp1[i][0] = Math.max(dp1[i-1][0],-prices[i]);
//j = 0
//j = 1
dp0[i][1] = Math.max(dp0[i-1][1],dp1[i-1][0]+prices[i]); // 保持 or 卖出
dp1[i][1] = Math.max(dp1[i-1][1],dp0[i-1][1]-prices[i]); // 保持 or 买入
//j = 2
dp0[i][2] = Math.max(dp0[i-1][2],dp1[i-1][1]+prices[i]); // 保持 or 卖出
}
return dp0[len-1][2];
}
}

空间优化

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int[] dp0 = new int[3];
int[] dp1 = new int[3];
dp1[0] = -prices[0];dp1[1] = -prices[0];dp1[2] = -prices[0];
for(int i = 1; i < len; i++) {
dp1[0] = Math.max(dp1[0],-prices[i]);
//j = 0
dp1[1] = Math.max(dp1[1],dp0[1]-prices[i]); // 保持 or 买入
dp0[1] = Math.max(dp0[1],dp1[0]+prices[i]); // 保持 or 卖出
dp0[2] = Math.max(dp0[2],dp1[1]+prices[i]); // 保持 or 卖出
}
return dp0[2];
}
}

4.买卖k次

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if(prices == null || len < 2 || k == 0) return 0;
if (k > len / 2) { // 当k很大时相当于不限制次数
int res = 0;
int hold = prices[0];
for (int i = 1; i < len; i++)
res += Math.max(0, prices[i] - prices[i - 1]);
return res;
}
int[][] dp0 = new int[len][k+1];
int[][] dp1 = new int[len][k+1];
for(int j = 0; j <= k; j++) dp1[0][j] = -prices[0]; // i = 0
for(int i = 1; i < len; i++) {
dp1[i][0] = Math.max(dp1[i-1][0],-prices[i]);
//j = 0
for(int j = 1; j <= k; j++) {
//j > 0
dp0[i][j] = Math.max(dp0[i-1][j],dp1[i-1][j-1]+prices[i]); // 保持 or 卖出
dp1[i][j] = Math.max(dp1[i-1][j],dp0[i-1][j]-prices[i]); // 保持 or 买入
}
}
return dp0[len-1][k];
}
}

空间优化

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2 || k == 0) return 0;
if (k > len / 2) { // 当k很大时相当于不限制次数
int res = 0;
int hold = prices[0];
for (int i = 1; i < len; i++)
res += Math.max(0, prices[i] - prices[i - 1]);
return res;
}
int[] dp0 = new int[k+1];
int[] dp1 = new int[k+1];
for(int j = 0; j <= k; j++) dp1[j] = -prices[0]; // i = 0
for(int i = 1; i < len; i++) {
dp1[0] = Math.max(dp1[0],-prices[i]);
//j = 0
for(int j = 1; j <= k; j++) {
//j > 0
dp1[j] = Math.max(dp1[j],dp0[j]-prices[i]); // 保持 or 买入
dp0[j] = Math.max(dp0[j],dp1[j-1]+prices[i]); // 保持 or 卖出
}
}
return dp0[k];
}
}

思路二：

用dp[i]代表在第i天卖出时的最大收益

我们可以分成两种情况：
1.保持现状（或理解为在第i天买入在第i天卖出）；
2.在第i天前某一天买入在第i天卖出；

1.买卖一次

状态转移方程：dp[i] = max(0, dp[i-1] + prices[i] - prices[i-1])
对于第一种情况：同一天买入卖出，收益为0；
对于第二种情况：dp[i-1]代表在第i-1卖出时的最大收益，如果不在第i-1天卖而是在第i天卖，则表示第i天卖出时的最大收益。
eg:3,3,5,6,7,0。
在第三天卖出时最大收益为5-3=2；在第四天卖出时的最大收益为：6-5+2=3，即相当于不在第三天卖而是在第4天卖6-3=3。

在从前往后更新dp时我们还需要用一个变量记录全局的最大获益

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int[] dp = new int[len];
int max_profit = 0;
for(int i = 1; i < len; i++) {
dp[i] = Math.max(0,prices[i]-prices[i-1]+dp[i-1]);
max_profit
= Math.max(max_profit,dp[i]);
}
return max_profit ;
}
}

空间优化：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int dp = 0;
int max_profit = 0;
for(int i = 1; i < len; i++) {
dp = Math.max(0,prices[i]-prices[i-1]+dp);
max_profit
= Math.max(max_profit,dp);
}
return max_profit ;
}
}

2.不限次数

dp[i] = dp[i-1] + max(0, prices[i] - prices[i-1])

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2) return 0;
int dp = 0;
for(int i = 1; i < len; i++) {
dp = dp + Math.max(0, prices[i] - prices[i-1]);
}
return dp;
}
}

3.买卖k次

复制代码

1
2
3
local[i][j]: 已买卖j次且在最后一次是在i天卖出的最大获益；
global[i][j]: 截止到第i天，买卖j次的最大获益；

状态转移方程：

复制代码

1
2
3
local[i][j] = max(global[i-1][j-1], prices[i] - prices[i-1] + local[i-1][j]); // 情况1 or 情况2
global[i][j] = max(global[i-1][j], local[i][j]);

对于第一种情况：同一天买入卖出，收益为global[i-1][j-1]+0；
对于第二种情况：local[i-1][j]代表在第i-1卖出时的最大收益，如果不在第i-1天卖而是在第i天卖，则表示第i天卖出时的最大收益。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(prices == null || len < 2 || k == 0) return 0;
if (k > len / 2) { // 当k很大时相当于不限制次数
int res = 0;
int hold = prices[0];
for (int i = 1; i < len; i++)
res += Math.max(0, prices[i] - prices[i - 1]);
return res;
}
int[] local = new int[k+1];
int[] global = new int[k+1];
for(int i = 1; i < len; i++) {
for(int j = 1; j <= k; j++) {
local[j] = Math.max(global[j-1],prices[i]-prices[i-1]+local[j]);
global[j] = Math.max(global[j],local[j]);
}
}
return global[k];
}
}