LeetCode-股票问题
2021-06-09 本文已影响0人
蒋斌文
LeetCode-股票问题
121. 买卖股票的最佳时机
难度简单
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 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。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
解题思路：
数组 prices 以每个i为卖出时机 遍历一遍数组 prices 求所有以i为卖出的最大值
- 假设 求index=0 表示当天买，当天卖 火里为0
- 以每个i为卖出时机，买入点为prices[0,i] 买入时机为prices[0,i]的最小值
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
// 0...i 最小值
int min = prices[0];
int ans = 0;
for (int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
ans = Math.max(ans, prices[i] - min);
}
return ans;
}
}
image-20210609091827504
122. 买卖股票的最佳时机 II
难度简单
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 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。
提示：
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
解题思路
- 遍历整个股票交易日价格列表
price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。
如果 prices[i] > prices[i-1] profit= prices[i] - prices[i-1]
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;
}
}
image-20210609092927921
123. 买卖股票的最佳时机 III
难度困难
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 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 <= prices.length <= 1050 <= prices[i] <= 105
解题思路
对于任意一天考虑四个变量:
fstBuy: 在该天第一次买入股票可获得的最大收益
fstSell: 在该天第一次卖出股票可获得的最大收益
secBuy: 在该天第二次买入股票可获得的最大收益
secSell: 在该天第二次卖出股票可获得的最大收益
分别对四个变量进行相应的更新, 最后secSell就是最大
收益值(secSell >= fstSell)
class Solution {
public int maxProfit(int[] prices) {
int fstBuy = Integer.MIN_VALUE, fstSell = 0;
int secBuy = Integer.MIN_VALUE, secSell = 0;
for(int p : prices) {
fstBuy = Math.max(fstBuy, -p);
fstSell = Math.max(fstSell, fstBuy + p);
secBuy = Math.max(secBuy, fstSell - p);
secSell = Math.max(secSell, secBuy + p);
}
return secSell;
}
}
image-20210609094939456
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int ans = 0;
int doneOnceMinusBuyMax = -prices[0];//完成一次交易 减去第二次买入后 的最大利润
int doneOnceMax = 0;// 0 : [0] - [0] 完成一次交易后 获取的最大利润，即股票问题一获取的收益
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
ans = Math.max(ans, doneOnceMinusBuyMax + prices[i]);//以i点 完成两次股票买卖，获取的最大收益 doneOnceMinusBuyMax + prices[i] 表示完成了第二次股票卖出
min = Math.min(min, prices[i]);//[0,i] 的最小值，最佳买入股票点
doneOnceMax = Math.max(doneOnceMax, prices[i] - min); //股票问题一的解 当天卖出最大收益
doneOnceMinusBuyMax = Math.max(doneOnceMinusBuyMax, doneOnceMax - prices[i]);//寻找第二次买入点
}
return ans;
}
}
image-20210609095110345
188. 买卖股票的最佳时机 IV
难度困难
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 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 。
提示：
0 <= k <= 1000 <= prices.length <= 10000 <= prices[i] <= 1000
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n == 0) return 0;
if(k >= prices.length/2) return greedy(prices);
int[][] dp = new int[k + 1][2];
for (int i = 1; i <= k; i++) {
dp[i][1] = Integer.MIN_VALUE;
}
for (int price : prices) {
for (int j = 1; j <= k; j++) {
dp[j][0] = Math.max(dp[j][0], dp[j][1] + price);// 买了卖
dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - price); // 卖了买
}
}
return dp[k][0];
}
private int greedy(int[] prices) {
int max = 0;
for(int i = 1; i < prices.length; ++i) {
if(prices[i] > prices[i-1])
max += prices[i] - prices[i-1];
}
return max;
}
}
image-20210609102657113
309. 最佳买卖股票时机含冷冻期
难度中等788收藏分享切换为英文接收动态反馈
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
- buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); （第一项表示第i-1天买进，第天不做买进操作，第二项表示第i天买进）
- sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); (第一项表示第i-1天卖出，第天不做卖出操作，第二项表示第i天卖出)
class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int N = prices.length;
int[] buy = new int[N];
int[] sell = new int[N];
buy[1] = Math.max(-prices[0], -prices[1]);
sell[1] = Math.max(0, prices[1] - prices[0]);
for (int i = 2; i < N; i++) {
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
}
return sell[N - 1];
}
}
image-20210609104709666
