【Leetcode】买卖股票的最佳时期系列题解

买卖股票的最佳时期这个系列一共有六道题目,难度分别为简单->中等->困难,每个难度有两道题目。

难度:简单

买卖股票的最佳时机(只能买卖一次)

题目链接

题目描述

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

样例输入

[7,1,5,3,6,4]

样例输出

5

样例解释

在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

解题思路

因为只允许进行一次交易,所以我们需要做的是维护区间的最大差值。我们使用min来表示区间的极小值,max来表示区间的极大值,在扫描数组的时候不断去维护max与min,每次更新max值计算一次差值,需要注意的点是在更新min值需要将max重置成max=min。因为我们不能用i天的min值来跟i-1天的max计算差值,这是属于未买先卖的情况。

AC代码

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(vector<int>& prices) {
int len = prices.size();
if (0 == len)
return 0;
int max, min, ans = 0;
min = max = prices[0];
for (int i = 1; i < len; i++){
if (min > prices[i]){
max = min = prices[i];
}
if (max < prices[i])
max = prices[i];
if (max - min > ans)
ans = max - min;
}
return ans;
}
};

买卖股票的最佳时机 II(买卖次数无限制)

题目链接

题目描述

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

样例输入

[7,1,5,3,6,4]

样例输出

7

样例解释

在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解题思路

这道题不限制交易次数。采用贪心的思想,维护区间的极小值跟极大值,在极大值卖出股票,极小值处买进股票,然后将所有极大值与极小值的差值想加起来便是答案了。

AC代码

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(vector<int>& prices) {

int len = prices.size();
if (0 == len)
return 0;
int max, min, ans = 0;
min = max = prices[0];
for (int i = 1; i < len; i++){
if (max > prices[i]){
ans += max - min;
max = min = prices[i];
}else if (max < prices[i]){
max = prices[i];
}
if (min > prices[i])
max = min = prices[i];
}
ans += max - min;
return ans;
}
};

难度:中等

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

题目链接

题目描述

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

样例输入

[1,2,3,0,2]

样例输出

3

样例解释

对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路

这道题目似乎没有办法进行贪心解决,唯有将目光转向动态规划。题目已经帮我们将三种状态总结了出来

  1. 目前持有股票(这个状态)
  2. 目前处于冷却器
  3. 目前没有持有股票

定义一个dp[i][j]数组,i表示天数,j表示状态,0代表处于冷冻期,1代表卖出,2买入
冷冻期可以由前一天已经是冷冻期或者在前一天发生卖出股票得到:

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

持有股票可以由当天买入股票或者i-1天已经持有股票得到

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

卖出股票可以由当天卖出股票或者i-1天已经卖出股票得到

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

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (0 == len)
return 0;
int dp[len][3];
//0代表处于冷冻期,1代表卖出,2买入
memset(dp, 0, sizeof(dp));
dp[0][2] = -prices[0];
for (int i = 1; i < len; i++){
dp[i][0] = max(dp[i-1][0],dp[i - 1][1]);
dp[i][1] = max(dp[i-1][1], dp[i-1][2] + prices[i]);
dp[i][2] = max(dp[i-1][2], dp[i-1][0] - prices[i]);
}
return max(dp[len-1][0], dp[len-1][1]);
}
};

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

题目链接

题目描述

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每次交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

样例输入

prices = [1, 3, 2, 8, 4, 9], fee = 2

样例输出

8

样例解释

能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

解题思路

这道题跟买卖股票的最佳时机 II相比较,只是多了一个手续费的限制条件,两道题的解法很相似,只是这道题在交易是多了一些判断条件
我们先来思考一下如果出现一个1,5,1,6的序列我们到底是选择一次交易还是两次交易。我们不妨将这四个值分别定义为min_1, max_1, min_2, max_2,手续费为fee。
进行一次交易的收益为:max_2 - min_1 - fee
进行两次交易的收益为:max_2 - min_2 - fee + (max_1 - min_1 -fee),化简为:max_2 - min_1 -fee + (max_1 - min_2 -fee)
所以我们只需要判断max_1 - min_2 - fee > 0即可得到该选择一次交易还是两次交易
注意:在进行交易时我们需要判断极大值与极小值的差值是否比手续费大,咱们不做亏本的买卖

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size();
if (0 == len)
return 0;
int max, min, ans = 0;
min = max = prices[0];
for (int i = 1; i < len; i++){
if (max - prices[i] - fee > 0 && max - min - fee > 0){
ans += max - min - fee;
max = min = prices[i];
}else if (max < prices[i]){
max = prices[i];
}
if (min > prices[i]) {
max = min = prices[i];
}
}
if (max - min - fee > 0)
ans += max - min - fee;
return ans;
}
};

难度:困难

买卖股票的最佳时机 III

题目链接

题目描述

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

样例输入

[3,3,5,0,0,3,1,4]

样例输出

6

样例解释

在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

解题思路

根据买卖股票的最佳时机的思路,从前往后求一次前缀数组,然后再从后往前求一次后缀数组,然后我们将前缀数组和后缀数组进行一次求和操作找到最大值即可

AC代码

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
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (0 == len)
return 0;
int maxs, mins;
int pre[len], after[len];
mins = maxs = prices[0];
pre[0] = after[len - 1] = 0;
for (int i = 1; i < len; i++){
if (mins > prices[i]){
maxs = mins = prices[i];
}
if (maxs < prices[i])
maxs = prices[i];
pre[i] = pre[i-1];
if (maxs - mins > pre[i])
pre[i] = maxs - mins;
}
mins = maxs = prices[len-1];
for (int i = len - 2; i > -1; --i){
if (maxs < prices[i])
mins = maxs = prices[i];
if (mins > prices[i])
mins = prices[i];
after[i] = after[i + 1];
if (maxs - mins > after[i])
after[i] = maxs - mins;
}
int ans = max(pre[len-1], after[0]);
for (int i = 1; i < len - 1; i++){
ans = max(ans, pre[i - 1] + after[i]);
}
return ans;
}
};

买卖股票的最佳时机 IV

题目链接

题目描述

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

样例输入

[3,2,6,5,0,3], k = 2

样例输出

7

解题思路

这毫无疑问又是一道动态规划问题。定义一个dp[k][j],k代表第几次交易,j代表买入还是卖出,0是买入,1是卖出。也许有同学有疑问,不需要表示天数吗,但是熟悉02背包的同学都是知道这里是可以省略一维数组的。不明白的同学可以去看一下背包九讲里的02背包这里就不做太多02背包的解释了。
在i天进行第j次买入的状态转移方程为dp[j][1] = max(dp[j][1], dp[j][0] + prices[i]);
在i天进行第j次卖出的状态转移方程为dp[j][0] = max(dp[j][0], dp[j-1][1] - prices[i]);
这道题目有一个比较大的坑点就是k可能会很大,所以我们需要对k做一个判断。如果k大于等于数组长度的一半,那就说明我们可以将这组数据当做没有限制购买次数来处理。

AC代码

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
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
if (0 == len)
return 0;
if (k > (len >> 1)){
int max, min, ans = 0;
min = max = prices[0];
for (int i = 1; i < len; i++){
if (max > prices[i]){
ans += max - min;
max = min = prices[i];
}else if (max < prices[i]){
max = prices[i];
}
if (min > prices[i])
max = min = prices[i];
}
ans += max - min;
return ans;
}
int dp[k + 1][2];
//0是买入,1是卖出
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= k; i++){
dp[i][0] = -prices[0];
}
for (int i = 1; i < len; i++){
for (int j = k; j > 0; j--){
dp[j][1] = max(dp[j][1], dp[j][0] + prices[i]);
dp[j][0] = max(dp[j][0], dp[j-1][1] - prices[i]);

}
}
return dp[k][1];
}
};
-------------本文结束您的阅读与肯定是我持续装*的最大动力-------------