- 股票买卖最佳时机
- 一、[121. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
- 解法一：暴力法，（时间超限制）
- 解法二：一次遍历
- 解法三：动态规划（二维数组）
- 解法四：动态规划（空间复杂度的优化一）
- 解法五：动态规划（空间复杂度的优化二）
- 二、[122. 买卖股票的最佳时机 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)
- 2.1 解法一：贪心算法
- 2.2 解法二：动态规划
- 2.3 解法三：动态规划（空间复杂度优化）
- 三、[123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)
- 3.1 解法一：转换成第一题（时间超限制）
- 3.2 解法二：动态规划
- 四、[309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)
- 4.1 动态规划
- 4.2 动态规划（空间优化）
- 五、[188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)
- 5.1 动态规划：是[123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/) 问题的扩展
- 六、[714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
- 6.1 动态规划
- 6.2 动态规划（空间优化）
在一个数组中找到两个值：后一个值减去前一个值，差值最大。
解法一：暴力法，（时间超限制） public int maxProfit(int[] prices) {
int res = 0;
for (int i=0; ires) {
res = prices[j] - prices[i];
}
}
}
return res;
}
解法二：一次遍历
public int maxProfit(int[] prices) {
int minV = Integer.MAX_VALUE;
int res = 0;
for (int i=0; iprices[i]) {
minV = prices[i];
}else if (prices[i]-minV>res) {
res = prices[i]-minV;
}
}
return res;
}
解法三：动态规划（二维数组）
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
// dp[i][0] 不持有股票、dp[i][1] 持有股票
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = 0-prices[0];
for (int i=1; i
解法四：动态规划（空间复杂度的优化一）
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int[][] dp = new int[2][2];
// dp[i][0] 不持有股票， dp[i][1] 持有股票
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i=1; i
解法五：动态规划（空间复杂度的优化二）
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int notGP = 0;
int hasGP = -prices[0];
for (int i=1; i
二、122. 买卖股票的最佳时机 II
2.1 解法一：贪心算法
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int res = 0;
for (int i=1; iprices[i-1]) {
res += prices[i]-prices[i-1];
}
}
return res;
}
2.2 解法二：动态规划
dp[i][0] 持有现金；dp[i][1] 持有股票
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int[][] dp = new int[n][2];
// 持有股票
dp[0][0] = 0;
// 持有现金
dp[0][1] = -prices[0];
for (int i=1; i
2.3 解法三：动态规划（空间复杂度优化）
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int notGP = 0;
int hasGP = -prices[0];
for (int i=1; i
三、123. 买卖股票的最佳时机 III
3.1 解法一：转换成第一题（时间超限制）
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int res = 0;
for (int i=1; i=hi) return 0;
int notGP=0;
int hasGP=-prices[lo];
for (int i=lo+1; i<=hi; i++) {
notGP = Math.max(notGP, hasGP+prices[i]);
hasGP = Math.max(hasGP, -prices[i]);
}
return notGP;
}
3.2 解法二：动态规划
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for (int i=1; i
四、309. 最佳买卖股票时机含冷冻期
4.1 动态规划
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
int[][] dp = new int[n][3];
// dp[i][0] 持有股票
// dp[i][1] 今天卖出后，处于冷冻期
// dp[i][2] 不持有股票，并且不处于冷冻期
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
for (int i=1; i
4.2 动态规划（空间优化）
public int maxProfit(int[] prices) {
int n = prices.length;
if (n<2) return 0;
// 今天买入股票
int hasGP = -prices[0];
// 今天售出股票
int sellGP = 0;
// 今天不持有股票
int notGP = 0;
for (int i=1; i
五、188. 买卖股票的最佳时机 IV
5.1 动态规划：是123. 买卖股票的最佳时机 III 问题的扩展
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n<2 || k<1) return 0;
// dp[i][0] 第i次买， dp[i][1] 第i次卖
int[][] dp = new int[k][2];
for (int j=0;j
六、714. 买卖股票的最佳时机含手续费
6.1 动态规划
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
if (n<2) return 0;
// dp[i][0] 不持有股票， dp[i][1] 持有股票
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i=1; i
6.2 动态规划（空间优化）
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
if (n<2) return 0;
int hasGP = -prices[0];
int notGP = 0;
for (int i=1; i 
