【LeetCode-面试-股票问题】算法中所有股票问题汇总_股票问题编程

  股票问题是我们常见的算法问题，因为它可以考察我们对算法的理解以及我们的编程思维方式，同时它也是贪心算法跟动态规划的高度体现！下面是LeetCode上面所有的股票问题！

`下面两个核心方程！

第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
i代表天，k代表交易次数，0代表不持有也就是sell，1代表持有也就是buy！

`

121.买卖股票的最佳时机（easy）限定交易次数 k=1

原题：

给定一个数组 prices ，它的第i个元素prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

• 来源：力扣（LeetCode）
• 难度：简单
• 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

解法

121题限制条件：一次交易机会
那么我们目的是求出合适的买入和卖出机会，然后获得的最大利润！
因此，我们需要两个关键值，一个是最小的买入值buy，另一个是最大的利润sell！

• 必须是先买入才能卖出，所以初始化第一天买入，然后第二天卖出
• 循环求取每天的最大的sell和最小buy

 public int maxProfit(int prices[]) {
        int sell = 0;
        int buy = -prices[0];//假设第一天买了
        for (int i=1;i<prices.length;i++){
            sell = Math.max(sell,buy+prices[i]);//不持有，即该天的卖出，求最大利润,卖出所以是加价格
           buy = Math.max(buy,-prices[i]);//持有，即当天买入，就负的价格 -prices，
                                         // 最小买入，因为buy是负的，所以其最大就是价格最小
        }
        return sell;
    }
1
2
3
4
5
6
7
8
9
10

---

122.买卖股票的最佳时机 II（medium）交易次数无限制 k = +infinity

原题：

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

• 来源：力扣（LeetCode）
• 难度：中等
• 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

解法

122 题限制：交易次数无限制 k = +infinity
这是经典贪心算法。

• 求最大利润，我们其实只需要考虑交易为正的情况，也就是说只要交易是正收益，就可以进行
• 因为不限制交易次数，所以卖出的时候还可以买入，买入前也可以卖出
• 因此，只需要将收益为正的值纳入总和即可

 public int maxProfit2(int prices[]) {
        int resSell = 0;
        for (int i=0;i<prices.length-1;i++){
            int tmp = prices[i+1]-prices[i];//卖出前必须买入。则后一天减前一天
            if(tmp>=0){//大于0，表示此次交易为正，可进行交易
                resSell+=tmp;//利润加入总和
            }
        }
        return resSell;
    }
1
2
3
4
5
6
7
8
9
10

也可以使用跟121题类似的方法

• 假设第一次买入
• 计算每次的最大买入、卖出
• 因为是无限交易，所以买入时，我们需要带入sell总额
• 第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来
• 第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来
• sell为该天不持有，buy为该天持有

 public int maxProfit2(int prices[]) {
  		int sell = 0;
        int buy = -prices[0];//假设第一天买了
        for (int i=1;i<prices.length;i++){
           sell = Math.max(sell,buy+prices[i]);不持有，即该天的卖出，求最大利润,卖出所以是加价格
             buy = Math.max(buy,sell-prices[i]);//持有，即当天买入，就负的价格 -prices，
                                                //又因为该天不持有时sell可能不为0，所以考虑总的收益所以得加入sell-价格
        }
        return sell;
  }
1
2
3
4
5
6
7
8
9
10

---

123.买卖股票的最佳时机 III (hrad) 限定交易次数 k=2

原题：

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

• 来源：力扣（LeetCode）
• 难度：困难
• 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

解法

在任意一天结束之后，我们会处于以下五个状态中的一种：
1.未进行过任何操作；
2.只进行过一次买操作；
3. 进行了一次买操作和一次卖操作，即完成了一笔交易；
4.在完成了一笔交易的前提下，进行了第二次买操作；
5.完成了全部两笔交易。
由于第一个状态的利润显然为 0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为buy1,sell1,buy2,sell2

• 对于buy1 而言，在第 i 天我们可以不进行任何操作，保持不变，也可以在未进行任何操作的前提下以prices[i] 的价格买入股票
• 对于sell1而言，在第 ii 天我们可以不进行任何操作，保持不变，也可以在只进行过一次买操作的前提下以prices[i] 的价格卖出股票
• 同理我们可以得到buy2,sell2

//注意最后一次交易持有时考虑第一次交易的sell
    public int maxProfit3(int prices[]) {
        int n = prices.length;
        int sell1 = 0;//dp[i][2][0]
        int buy1 = -prices[0];//第一次交易的dp[i][2][1]
        int sell2 = 0;//dp[i][1][0]
        int buy2 = -prices[0];//第2次交易的dp[i][1][1]
        for (int i= 1;i<n;i++ ){
            sell2 = Math.max(sell2,buy2+prices[i]);//最后一次交易（不持有）
            buy2 = Math.max(buy2,sell1-prices[i]);//最后一次持有，因为该天不持有时，有第一次交易sell1的值，所以带入
            sell1=Math.max(sell1,buy1+prices[i]);//第一次交易(不持有)
            buy1 = Math.max(buy1,-prices[i]);//第一次持有，sell为0，所以0-prices[i]
        }
        return sell2;//最后交易后的利润为总利润
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

188. 买卖股票的最佳时机 IV (hard) 限定交易次数 最多次数为 k

原题：

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

• 来源：力扣（LeetCode）
• 难度：困难
• 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv

解法

• 先确定k值，因为k最大为prices总天数的一半；
• 初始化buy和sell的数组，k+1，因为k次交易，第一次交易前得进行初始化；
• 交易前初始化buy[0],sell[0]
• 初始化k次交易的值，都为最小值的一半，防止越界
• 遍历价格，开始交易，确定首次交易前的buy最小，然后进行k次交易，找到最大利润

 public int maxProfit4(int k,int prices[]) {
        if(prices.length==0){
            return 0;
        }

        int n = prices.length;
        k = Math.min(k,n/2);//k最大为总天数的一半
        int[] buy = new int[k+1];
        int[] sell  = new int[k+1];

        buy[0] = -prices[0];//交易前的买入
        sell[0] = 0;//交易前的利润为0
        for (int i =1;i<=k;i++){//初始K次交易，为最小。防止越界
            buy[i] = sell[i]= Integer.MIN_VALUE/2;
        }

        for(int i=1;i<n;++i){//遍历价格，开始交易
            buy[0] = Math.max(buy[0], sell[0] - prices[i]);//确定交易前的最小买入
            for (int j = 1; j <= k; ++j) {//开始k次交易
                buy[j] = Math.max(buy[j], sell[j] - prices[i]);//第j次买入的最小
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);//第j次交易的利润
            }
        }
        return Arrays.stream(sell).max().getAsInt();
    }
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

---

309. 最佳买卖股票时机含冷冻期(medium) 含有交易冷冻期

原题：

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

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

• 来源：力扣（LeetCode）
• 难度：中等
• 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

解法

存在冷冻期，就要考虑冷冻期的利润和不在冷冻期的利润

• 手上持有股票的最大收益
• 手上不持有股票，并且处于冷冻期中的累计最大收益
• 手上不持有股票，并且不在冷冻期中的累计最大收益
• 该天持有（今天买入才会持有，当前应该执行买入）=前一天持有不操作 和 前一天不持有买入（前一天不持有的话，前一天就是冷冻期，那么今天就不再冷冻期，就用不在冷冻期最大利润-价格））
• 该天冷冻期利润（交易后才是冷冻期，当前应该进行卖出） = （今天是冷冻期那么肯定是交易后变冷冻）buy+卖出价格
• 该天不在冷冻期（那么当前肯定是冷冻，当前冷冻不进行操作） = (今天不是冷冻期，由冷冻期过后才解冻)应该跟冷冻期比较获得最大利润

public int maxProfit5(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int n= prices.length;
        int buy = -prices[0];//手上持有股票的最大收益
        int sellC = 0;//手上不持有股票，并且处于冷冻期中的累计最大收益
        int sellO =0;//手上不持有股票，并且不在冷冻期中的累计最大收益

        for (int i =1;i<n;i++){
            int newbuy = Math.max(buy,sellO-prices[i]);//该天持有（今天买入才会持有，当前应该执行买入）=前一天持有不操作 和 前一天不持有买入
                                                        // （前一天不持有的话，前一天就是冷冻期，那么今天就不再冷冻期，就用不在冷冻期最大利润-价格）
            int newsellC = buy+prices[i];//该天冷冻期利润（交易后才是冷冻期，当前应该进行卖出） = （今天是冷冻期那么肯定是交易后变冷冻）buy+卖出价格
            int newsellO =Math.max(sellC,sellO);//该天不在冷冻期（那么当前肯定是冷冻，当前冷冻不进行操作） = (今天不是冷冻期，由冷冻期过后才解冻)应该跟冷冻期比较获得最大利润
            buy =newbuy;
            sellC=newsellC;
            sellO=newsellO;
        }
        return Math.max(sellC,sellO);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

714. 买卖股票的最佳时机含手续费 (medium) 每次交易含手续费

原题：

给定一个整数数组prices，其中第i个元素代表了第i天的股票价格 ；整数fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续

• 来源：力扣（LeetCode）
• 难度：中等
• 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

解法

无限次交易次数，但是每次卖出有手续费！

• 我们可以将卖出的手续算进在买入的价格里！
• 遍历所有价格
• 当 当前价格+手续费大于我们的买入价格buy（买入价格+fee）时，那么我们的买入价格就是偏贵的，应该选择此次的买入价格！
• 当 当前价格大于我们的buy（买入价格+fee），证明此次交易会使我们收益的，所以直接进行卖出，同时我们又可以免手续买入

 //当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利
    public int maxProfit6(int[] prices, int fee) {
        if (prices.length==0){
            return 0;
        }
        int n = prices.length;
        int buy = prices[0]+fee;//买入的价格和即将卖出的手续费
        int profit =0;//总收益
        for (int i =1;i<n;i++){
            if(prices[i]+fee <buy){//当前买入价格更低，则更换买入时机
                buy = prices[i]+fee;
            }else if(prices[i]>buy){//当前价格大于买入价格，证明收益为正，则卖出
                profit+=prices[i]-buy;
                buy = prices[i];//假设又买入，准备下次比较
            }
        }
        return profit;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18