Leetcode.买卖股票的最佳时机(系列)

Leetcode.买卖股票的最佳时机(系列)

Leetcode的打卡题目这个系列挺有意思的，现在自己复盘一轮，学习里面的思考算法，做点总结。

​

Level 1. 买卖股票的最佳时机

1.1 题目说明

给定一个数组 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 <= 105

• 0 <= prices[i] <= 104

  ​

---

1.2 解答分析

• 获得最大的利润，想的就是最低买入，最高卖出即可。若是在前i天选择买入，想要达到最高的利润，**则一定会选择价格最低的交易日买入。**这里可以用到算法的思想是：贪心算法。遍历价格列表prices并执行两步：

  由于初始值i=0 ，为了序号对应，本文设从第 0 天开始；

  1. 更新前i天的最低价格，即最低买入成本 cost；
  2. 更新前i天的最高利润 profit ，即选择「前 i−1天最高利润 profit 」和「第 i天卖出的最高利润 price - cost 」中的最大值 ；

• 用到for循环就行，找到最大值和最小值，接着和前一个状态比较利润的大小即可。

  ​

---

1.3 具体代码

class Solution {
    public int maxProfit(int[] prices) {
        int cost=Integer.MAX_VALUE,profit=0;
        for(int price:prices){
            cost=Math.min(cost,price);//找到最小的买入值
            profit=Math.max(profit,price-cost);//不断更新利润的最大值
        }
        return profit;
    }
}

class Solution{
    	//也同样可以利用动态规划进行解答，我们需要判断的是当前是否持有股票即可
    public int maxProfit(int[] prices){
        if(prices==null || prices.length==0){
            return 0;
        }
        int length=prices.length;
        
        //dp[i][0]代表的是第i天持有股票的最大收益
        //dp[i][1]代表的是第i天不持有股票的最大收益
        int[][] dp=new int[length+1][2];
        dp[0][0]=-prices[0]; //第一天持有的话，说明直接买入
        dp[0][1]=0; //不持有即为0
        for(int i=1;i<length;i++){
            dp[i][0]=Math.max(dp[i-1][0],-prces[i]); //买入则说明就是当前的股票得到的现金
            dp[i][1]=Math.max(dp[i-1][0]+priecs[i],dp[i-1][1]);
        }
        return dp[length-1][1]; //不持有股票的状态一定比持有的情况多
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$，$n$的长度即为数组的长度。

  • 空间复杂度：$O(1)$，未引入新的存储空间。

    ​

---

Level 2. 买卖股票的最佳时机 II

2.1 题目说明

给你一个整数数组 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 。
     总利润为 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 <= prices.length <= 3 * 104

• 0 <= prices[i] <= 104

  ​

---

2.2 解答分析

• 遍历整个股票交易日价格列表price，并执行贪心策略：所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。

• 设 tmp为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1];
  当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为 0 或为负，则直接跳过；
  遍历完成后，返回总利润 profit。

• 由于最多只能有一股股票，也就是每天都是买或不买。但是如果第i天买入，那么后续天只能选择卖出，从而赚取差值作为利润。

• 和Level1的区别：本题是总天数的累计总利润最大，而不是全部天数计算差值最大的2天

  ​

---

2.3 具体代码

//思路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;
    }
}

//思路2：和思路1雷同，但是代码可能好理解一些
class Solution {
    public int maxProfit(int[] prices) {
        int min=prices[0],max=prices[0],ans=0;
        for(int i=0;i<prices.length;i++){
            if(max>prices[i]){//不断找到较大的值
                ans+=max-min;
                max=prices[i];
                min=prices[i];
            }else{//相等的时候左指针不动，右指针右移
                max=prices[i];
            }
        } 
        ans+=max-min;//包含最后一位的卖出可能存在的差值，如[1,2,3,4,5]，最后max等于5，此时min等于1，最后需要做差
        return ans;
    }
}

//思路3：动态规划,这里做简单地处理，给出状态转移方程，分为持有和不持有的两种状态
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;//不持有（第0天）
        dp[0][1] = -prices[0];//持有（第0天）
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); //对于今天不持有，可以从两个状态转移过来：1. 昨天也不持有；2. 昨天持有，今天卖出。两者取较大值。

            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//对于今天持有，可以从两个状态转移过来：1. 昨天也持有；2. 昨天不持有，今天买入。两者取较大值。
        }
        return dp[n - 1][0];
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$

    ​

---

Level 3. 买卖股票的最佳时机 III

3.1 题目说明

给定一个数组，它的第 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 <= 105

• 0 <= prices[i] <= 105

  ​

---

3.2 解答分析

• 动态规划，前两个级别都是可以用暴力和贪心进行解答，但是本阶段开始就需要利用到动态规划了

• 一般的动态规划题目思路三步走：

  1. 定义状态转移方程
  2. 给定转移方程初始值
  3. 写代码递推实现转移方程

• 状态定义：dp[i][j][k] 表示在 [0, i] 区间里（状态具有前缀性质），交易进行了 j 次，并且状态为 k 时我们拥有的现金数。其中 j 和k的含义如下：

  • j = 0 表示没有交易发生；j = 1表示此时已经发生了 111 次买入股票的行为； j = 2 表示此时已经发生了 222 次买入股票的行为。即我们 人为规定 记录一次交易产生是在 买入股票 的时候。

  • k = 0 表示当前不持股； k = 1 表示当前持股。

• 思考初始化：

  • 下标为 0这一天，交易次数为 0、1、2并且状态为 0 和 1的初值应该如下设置：
  • dp[0][0][0] = 0：这是显然的；
  • dp[0][0][1]：表示一次交易都没有发生，但是持股，这是不可能的，也不会有后序的决策要用到这个状态值，可以不用管；
  • dp[0][1][0] = 0：表示发生了 1次交易，但是不持股，这是不可能的。虽然没有意义，但是设置成 0 不会影响最优值；
  • dp[0][1][1] = -prices[0]：表示发生了一次交易，并且持股，所以我们持有的现金数就是当天股价的相反数；
  • dp[0][2][0] = 0：表示发生了 2次交易，但是不持股，这是不可能的。虽然没有意义，但是设置成 0不会影响最优值；
  • dp[0][2][1] = 负无穷：表示发生了 2次交易，并且持股，这是不可能的。注意：虽然没有意义，但是不能设置成 0，这是因为交易还没有发生，必须规定当天 k 状态为 1（持股），需要参考以往的状态转移，一种很有可能的情况是没有交易是最好的情况。
  • 说明：dp[0][2][1] 设置成为负无穷这件事情我可能没有说清楚。大家可以通过特殊测试用例 [1, 2, 3, 4, 5]，对比 dp[0][2][1] = 0 与 dp[0][2][1] = 负无穷 的状态转移的差异去理解。

• 注意：只有在之前的状态有被赋值的时候，才可能有当前状态。

• 思考输出：最后一天不持股的状态都可能成为最大利润。

  ​

---

3.3 具体代码

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 第 2 维的 0 没有意义，1 表示交易进行了 1 次，2 表示交易进行了 2 次
        // 为了使得第 2 维的数值 1 和 2 有意义，这里将第 2 维的长度设置为 3
        int[][][] dp = new int[len][3][2];

        // 理解如下初始化
        // 第 3 维规定了必须持股，因此是 -prices[0]
        dp[0][1][1] = -prices[0];
        // 还没发生的交易，持股的时候应该初始化为负无穷
        dp[0][2][1] = Integer.MIN_VALUE;

        for(int i=1;i<len;i++){
            //如果今天要持有股票，应该比较继续持有昨天的股票好，还是今天才开始买股票好
            //(此时只交易了一次，所以是今天才买入的)
            dp[i][1][1]=Math.max(dp[i-1][1][1],-prices[i]);
            
            //如果今天持有现金，应该比较昨天持有现金好，还是昨天持有股票加上今天的股价好
            dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
            
            //如果今天要持有股票，应该比较继续持有昨天股票好，还是今天才开始买股票好
            //(此时交易了两次，所以用昨天的现金买股票)
            dp[i][2][1]=Math.max(dp[i-1][2][1],dp[i-1][1][0]-prices[i]);
            
            //如果今天要持有现金，应该比较昨天持有现金好，还是昨天持有股票加上今天的股价好
            dp[i][2][0]=Math.max(dp[i-1][2][0],dp[i-1][2][1]+prices[i]);
        }
        return Math.max(dp[len - 1][1][0], dp[len - 1][2][0]);
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$，$n$为股票价格数组的长度

  • 空间复杂度：$O(n)$，$n$为股票价格数组的长度

    ​

---

//上述的做法也可以转化为二维数组进行解决：
// 版本一
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }

        return dp[len - 1][4];
    }
}

// 版本二: 空间优化
class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[4]; 
        // 存储两次交易的状态就行了
        // dp[0]代表第一次交易的买入
        dp[0] = -prices[0];
        // dp[1]代表第一次交易的卖出
        dp[1] = 0;
        // dp[2]代表第二次交易的买入
        dp[2] = -prices[0];
        // dp[3]代表第二次交易的卖出
        dp[3] = 0;
        for(int i = 1; i <= prices.length; i++){
            // 要么保持不变，要么没有就买，有了就卖
            dp[0] = Math.max(dp[0], -prices[i-1]);
            dp[1] = Math.max(dp[1], dp[0]+prices[i-1]);
            // 这已经是第二次交易了，所以得加上前一次交易卖出去的收获
            dp[2] = Math.max(dp[2], dp[1]-prices[i-1]);
            dp[3] = Math.max(dp[3], dp[2]+ prices[i-1]);
        }
        return dp[3];
    }
}

​

Level 4. 买卖股票的最佳时机 IV

4.1 题目说明

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

提示：

• 1 <= k <= 100

• 1 <= prices.length <= 1000

• 0 <= prices[i] <= 1000

  ​

---

4.2 解答分析

1. 确定dp数组以及其下标的含义

• 定义这样的二维数组dp[i][j]：第i天的状态为j，此时所剩余的最大现金是dp[i][j];
• j的状态表示为：
  • 0 表示不操作
  • 1 第一次买入
  • 2 第一次卖出
  • 3 第二次买入
  • 4 第二次卖出
  • …
• 题目要求的最多K笔交易，那么此时的j的范围就是2*k+1即可。

2.确定递推公式

dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票

• 达到dp[i][1]状态，有两个具体操作：

  • 操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
  • 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

  选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

• 同理此时可以达到后续的剩余状态。区别就是这里要类比j为奇数是买，偶数是卖的状态。

3. dp数组的初始化

• dp[0][0]=0;
• dp[0][1]=-prices[0];
• dp[0][2]=0;
• dp[0][3]=-prices[0];

可以看出规律，上述的操作的时候，在初始化的地方同样要类比j为偶数是卖、奇数是买的状态。

4. 确定遍历的顺序

• 从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

举例推导dp数组

• 以输入[1,2,3,4,5]，k=2为例。如下图所示：

  

• dp[prices.size() - 1][2 * k]即红色部分就是最后求解。

  ​

---

4.3 具体代码

// 版本一: 三维 dp数组
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;

        // [天数][交易次数][是否持有股票]
        int len = prices.length;
        int[][][] dp = new int[len][k + 1][2];
        
        // dp数组初始化
        // 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润
        for (int i = 0; i <= k; i++) {
            dp[0][i][1] = -prices[0];
        }

        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= k; j++) {
                // dp方程, 0表示不持有/卖出, 1表示持有/买入
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[len - 1][k][0];
    }
}

// 版本二: 二维 dp数组
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;

        // [天数][股票状态]
        // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
        int len = prices.length;
        int[][] dp = new int[len][k*2 + 1];
        
        // dp数组的初始化, 与版本一同理
        for (int i = 1; i < k*2; i += 2) {
            dp[0][i] = -prices[0];
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k*2 - 1; j += 2) {
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[len - 1][k*2];
    }
}

//版本三：一维 dp数组
class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        if(k == 0){
            return 0;
        }
        // 其实就是123题的扩展，123题只用记录2次交易的状态
        // 这里记录k次交易的状态就行了
        // 每次交易都有买入，卖出两个状态，所以要乘 2
        int[] dp = new int[2 * k];
        // 按123题解题格式那样，做一个初始化
        for(int i = 0; i < dp.length / 2; i++){
            dp[i * 2] = -prices[0];
        }
        for(int i = 1; i <= prices.length; i++){
            dp[0] = Math.max(dp[0], -prices[i - 1]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
            // 还是与123题一样，与123题对照来看
            // 就很容易啦
            for(int j = 2; j < dp.length; j += 2){
                dp[j] = Math.max(dp[j], dp[j - 1] - prices[i-1]);
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i - 1]);
            }
        }
        // 返回最后一次交易卖出状态的结果就行了
        return dp[dp.length - 1];
    }
}