leetcode刷题笔记，买卖股票的最佳时机，问题汇总。
121.买卖股票的最佳时机1
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
1
2
3
4
5
6
7
8
9
10
| 示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
|
思路
暴力
暴力思路就是两层for循环，计算最大的差值，就是得到的最大利润
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
maxProfit = max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit;
}
};
|
时间复杂度是O(N^2)，会超时
贪心
贪心算法，思路是枚举当前数之前的最小值，计算当前数得到的利润的最大值。
- 用一个元素来记录最小值，每一次遍历都更新这个最小值（最小的买入价格）
- 用一个元素来记录得到的最大利润，每一次遍历都更新最大利润（当前价格减去最小买入价格）
首先更新的是最大利润，再更新最小买入价格，这样能保证最小买入价格的值一定是当前元素之前的某一个值，计算出来的最大利润才有效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxProfit = -1;
int minPrice = prices[0];
for (auto& i : prices) {
maxProfit = max(maxProfit, i - minPrice);
minPrice = min(minPrice, i);
}
return maxProfit;
}
};
|
动态规划
动态规划就要记住解题的几个步骤。
- 确定动归数组每个下标的含义
- 确定迭代方程
- 确定初始值
- 确定遍历顺序
- 举例推导
对于这道题而言，每天都有两种状态：今天持有股票和今天卖出股票。
我们可以设定dp[i][0]是第i天持有股票时的得到的最多钱，dp[i][1]是第i天不持有股票时得到的最多钱。很容易发现每天不持有股票得到的钱是更多的，所以最终的答案就是dp[prices.size()-1][1]，即这个二维数组的右下角。
这里就需要两个递推公式了，先看第i天持有股票的钱
- 上一天就持有股票，即保持
dp[i-1][0]不变； - 今天才持有股票（买入），即
-price[i]，本题股票只能买入一次，所以选择今天买入，那么剩下的钱就是0减去股票的价格；
可得 dp[i][0] = max(dp[i-1][0],-price[i])，上两种情况的最大值。
第i天不持有股票的钱也分为两种情况
- 上一天就没有持有股票，即保持
dp[i-1][1]不变； - 今天才卖出股票，即保持
price[i]+dp[i-1][0]（因为今天卖出，所以上一天肯定是持有股票的）
可得递推公式 dp[i][1] = max(dp[i-1][1],price[i]+dp[i-1][0])；
初始化dp数组时，第0天肯定只能持有股票，不能卖出，所以初始化如下
1
2
| dp[0][0] = 0-price[0];
dp[0][1] = 0;
|
这里还有另外一个优化方向，从递推公式中可以看出，每一天的值只和上一天有关系，那么并不需要一个完整的二维数组，只需要一个2*2的数组就可以了，我们把今天的值写入上一天就OK了，这样可以把空间复杂度降为O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(2, vector<int>(2, 0));
dp[0][0] = 0-prices[0];
dp[0][1] = 0;
for (int i = 1; i < prices.size(); i++) {
dp[1][0] = max(0-prices[i], dp[0][0]);
dp[1][1] = max(prices[i] + dp[0][0], dp[0][1]);
dp[0][0] = dp[1][0];
dp[0][1] = dp[1][1];
}
return dp[1][1];
}
};
|
不过个人感觉这道题用动态规划来写实在是想不出来思路，而且还感觉很麻烦，还不如用贪心来处理一下。
122.买卖股票的最佳时机2
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
|
提示
1
2
| 1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
|
思路
动态规划
122题和121在动态规划上唯一的区别就是当天买入股票的时候，需要计算上一天卖出股票后能剩下的最多钱（因为同一天只能持有一张股票）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(2, vector<int>(2, 0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < prices.size(); i++) {
dp[1][0] = max(dp[0][1] - prices[i], dp[0][0]);
dp[1][1] = max(prices[i] + dp[0][0], dp[0][1]);
dp[0][0] = dp[1][0];
dp[0][1] = dp[1][1];
}
return dp[1][1];
}
};
|
贪心
122题在121的基础上新增了一个可以多次卖出+买入的操作。而121题只能买入一次+未来卖出一次。
因为每一天都可以买入+卖出，所以我们可以把利润拆分成每一天。只要某一天买入+明天卖出的利润是正数，那么就把他加入到最终结果中。这样就相当于排除亏钱的情况，只要能赚钱就买，即可计算出最大利润。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int maxProfit(vector<int>& prices) {
int count = 0;
for (int i = 1; i < prices.size(); i++) {
count += max(prices[i] - prices[i - 1], 0);
}
return count;
}
};
|
123.买卖股票的最佳时机3
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
|
提示
1
2
| 1 <= prices.length <= 105
0 <= prices[i] <= 105
|
思路
主要是需要列出可以购入两次一共会有多少种状态：
- 当天不做操作；
- 当天继续持有股票（可以是新买股票，也可能是昨天就买入股票了）；
- 当天不继续持有股票；
- 当天第二次持有股票；
- 当天不持有第二次的股票；
这五个状态已经包含了所有的情况，使用一个dp[prices.size()][5]的二维数组分别存放这五种情况的剩余钱的数量，我们要做的就是列出每一种状态的转移方程就可以了。
对于当天不做操作而言，啥事都不用干，所以dp[i][0] = dp[i-1][0]。
对于当天第一次持有股票，分为两种情况：
- 这个股票是昨天留下来的（昨天就买了），对应的是
dp[i-1][1]； - 这个股票是今天刚买的，对应的是
dp[i-1][0] - prices[i]，含义是昨天啥事没干的剩余余额减去当天股票的价格（买入）；
因为我们最终需要的是最多能赚的钱，所以要用max来取二者最大值。
对于当天第一次不持有股票，也分为两种情况：
- 昨天就不持有了，对应的是
dp[i-1][2]； - 昨天持有，今天卖出，对应的是
dp[i-1][0] + prices[i]，含义是昨天买入股票的剩余余额加上当前股票的价格（今天卖出）；
同样是用max来取二者的最大值。
对于第二次持有和不持有，都是用同样的方式分析的，得到的递推公式如下
1
2
3
4
5
6
7
|
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
有了状态转移方程，可以看到每一次都是依赖于dp[i-1]的情况，所以我们需要先对dp[0]进行初始化，再从下标1开始遍历整个数组。
对于第0天而言，我们只有两种选择，即当天买入一次股票，和当天买入第二次股票（我们买了第一次，卖掉，再买入第二次）
分别对应的是下面两个值，需要初始化为第0天股票的价格。
1
2
| dp[0][1] = 0 - prices[0];
dp[0][3] = 0 - prices[0];
|
因为第0天我们手头上是没钱的，所以买了股票之后余额就是负数了。
最终返回的最大值是最后一天第二次卖出的余额。因为只有第二次卖出，才
代码
以下是完整的代码
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
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) {
return 0;
}
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
dp[0][1] = 0 - prices[0];
dp[0][3] = 0 - prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.size() - 1][4];
}
};
|
时间复杂度是O(N)，空间复杂度是O(N)。注意空间复杂度是O(5*N)，我们二维数组的每一行长度是固定的，所以空间复杂度并不是N^2！
空间复杂度优化
因为每一次遍历其实只和i-1有关系，其实我们可以把这个二维数组给压缩成dp[2][5]，只不过每次操作之后都须需要把当前的结果dp[1]给复制到dp[0]去作为下一次的操作依赖。
这样做能将空间复杂度降到O(1)，因为我们的数组长度是固定值。代码如下
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) {
if (prices.size() == 0) {
return 0;
}
vector<vector<int>> dp(2, vector<int>(5, 0));
dp[0][1] = 0 - prices[0];
dp[0][3] = 0 - prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[1][0] = dp[0][0];
dp[1][1] = max(dp[0][1], dp[0][0] - prices[i]);
dp[1][2] = max(dp[0][2], dp[0][1] + prices[i]);
dp[1][3] = max(dp[0][3], dp[0][2] - prices[i]);
dp[1][4] = max(dp[0][4], dp[0][3] + prices[i]);
dp[0][0] = dp[1][0];
dp[0][1] = dp[1][1];
dp[0][2] = dp[1][2];
dp[0][3] = dp[1][3];
dp[0][4] = dp[1][4];
}
return dp[1][4];
}
};
|
leetcode官方题解给的是一个将二维数组压成一维的空间压缩方式，但是那个方式非常不好理解，我个人感觉学会第一种思路就够了。
188.买卖股票的最佳时机4
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
1
2
3
4
5
6
7
8
9
10
| 示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
|
提示
1
2
3
| 1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000
|
思路
这道题其实就是123题目的变体，在123题目中我们是可以交易两次，本题就是将这个2改成了k。所以我们只需要将123题目中的思路改成k个就可以了。
当k为2的时候，一共有5个情况；当k为3的时候，一共有7种情况，多出来的是第三次持有和第三次不持有；同理，当k为未知数的时候，可得情况总数是2*k+1；
- 当i为奇数的时候，代表第
i/2+1次持有； - 当i为偶数的时候，代表第
i/2次不持有；
观察123题目的状态转移方程，能很明显的发现每一层其实都依赖于前一种情况，也就是二维数组中的前一列。根据此，只需要上一个内层的循环去遍历情况，就能递推出最终最大的利润值。
代码
完整代码如下
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
| class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) {
return 0;
}
vector<vector<int>> dp(prices.size(), vector<int>(k * 2 + 1, 0));
for (int j = 1; j < dp[0].size(); j += 2) {
dp[0][j] = 0 - prices[0];
}
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = dp[i - 1][0];
for (int j = 1; j < dp[i].size(); j++) {
if (j % 2 == 1) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
}
}
}
return dp[prices.size() - 1][2 * k];
}
};
|
309.买卖股票的最佳时机含冷冻期
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
1
2
3
4
5
6
7
8
| 示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
|
提示
1
2
| 1 <= prices.length <= 5000
0 <= prices[i] <= 1000
|
思路
这道题还是需要把所有状态给列出来，然后再列出每个状态对应的相关状态。
首先要明确冷冻期的概念：卖出股票的第二天不能买入股票。但没有说买入股票的第二天不能卖出。即冷冻期只对卖出股票有效。
那么每一天的状态就会有四种情况，同样是用二维dp数组来对应每一种情况：
- 今天持有股票（今天买入或者保持持有状态）；
- 今天不持有股票（今天卖出股票）；
- 今天不持有股票（昨天甚至前天就已经卖了）；
- 今天是冷冻期，啥事干不了；
这里相比188题目省略了“当天啥事不干”的状态，因为这个状态没有必要记录，一直都是0。
下面要做的就是分析出这四种状态的转移方程。
今天持有股票的情况，分为今天买入和保持持有的状态，转移方程如下
1
2
3
4
5
6
|
dp[i][0] = max(dp[i-1][0],
max(dp[i-1][2]-prices[i],dp[i-1][3] - prices[i]));
|
今天卖出股票的情况，只有一种，那就是昨天持有+今天卖出股票的价格
1
| dp[i][1] = dp[i-1][0] + prices[i];
|
昨天甚至前几天就不持有股票了，就有很多种情况；比如昨天是冷冻期，或前天就卖出了。
1
2
3
|
dp[i][2] = max(dp[i-1][3],dp[i-1][2]);
|
今天是冷冻期，说明昨天肯定是卖出股票了，不会有其他情况
状态转移方程确定了，下面要处理的就是如何进行初始化了。因为我们状态转移方程是依赖于i-1的，所以肯定是从左往右遍历，且需要提前初始化下标0的数据。
还是比较好想的，第一天其实只有当前买入的情况，其他买入+卖出，还是冷冻期的情况都是0（第一天不可能是冷冻期），所以只需要初试化dp[i][0] = 0 - prices[0]就可以了。
代码
完整代码如下
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
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) {
return 0;
}
vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
dp[0][0] = 0 - prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][2] - prices[i],
dp[i - 1][3] - prices[i]));
dp[i][1] = dp[i - 1][0] + prices[i];
dp[i][2] = max(dp[i - 1][3], dp[i - 1][2]);
dp[i][3] = dp[i - 1][1];
}
return max(dp[prices.size() - 1][1],
max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));
}
};
|
714.买卖股票的最佳时机含手续费
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 示例 1：
输入：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
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
|
提示
1
2
3
| 1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
|
思路和代码
这道题其实是122的翻版，交易的时候多加一个手续费就行了。一次交易（买入+卖出）只需要交一次手续费，我们统一在卖股票的时候交手续费就ok了。
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) {
if (prices.size() == 0) {
return 0;
}
vector<vector<int>> dp(2, vector<int>(2, 0));
dp[0][0] = 0 - prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[1][0] = max(dp[0][0], dp[0][1] - prices[i]);
dp[1][1] = max(dp[0][1], dp[0][0] + prices[i] - fee);
dp[0][0] = dp[1][0];
dp[0][1] = dp[1][1];
}
return dp[1][1];
}
};
|
The end
你学废了吗？
爱发电
