买卖股票问题

​ 今天重新写了些动态规划和贪心的题目，买卖股票的问题在这两个方面还是挺经典的。买卖股票在力扣上有四种题目，难度也是有涉及到简单、中等和困难。既然写了那么多次这几道题目，索性就水一篇文章来总结下买卖股票题的做法吧

买卖股票的最佳时机

题目连接：买卖股票的最佳时机

描述：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4]
输出：5

​ 作为股票题的第一题很简单，根据题目的描述，由于只进行一次交易，所以只需找到最低价买入，最高价卖出就行了。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy = prices[0];
        int profit = 0;
        for(int i = 1;i < n;i++){
            buy = Math.min(buy,prices[i]);
            profit = Math.max(profit,prices[i]-buy);
        }
        return profit;
    }
}

​ 这题也可以用动态规划的做法来做，只不过上面的贪心算法会更加的快更容易想。这里也写上动态规划的代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][1] = -prices[0];
        for(int i = 1;i < n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[n-1][0];
    }
}

买卖股票的最佳时机 II

题目链接：买卖股票的最佳时机 II

描述：

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

输入：prices = [7,1,5,3,6,4]
输出：7

​ 这一题与股票1的差别在于没有限制最多交易的次数，即我们可以多次进行买卖，这一题动态规划的做法我觉得是相对比较容易想出来的，定义一个二维数组dp[n][2]，dp[i][0]表示当前不持有股票的最大利润，dp[i][1]表示当前持有股票的最大利润。dp[i][0]可以是之前不持有股票的利润，也可以是把之前的股票在当前卖出后的利润，取它们之间的最大值即可，dp[i][1]可以是之前持有股票的利润，也可以是在之前没有持有股票买入当前股票后的利润，也是取它们之间的最大值即可。就可以得出这么一个状态转移方程：

​ 状态方程得出来之后也很容易写出代码：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][1] = -prices[0];
        for(int i = 1;i < n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}

​ 这题也是可以用贪心的做法来做的，我们可以把利润的获取拆分开来，假设我们有1、5、6这三个价格，一眼看上去我们是在价格为1时买入，价格为6时卖出，我们可以把这个过程看成在5的时候价格比1高，我们在5卖出，卖出后再把5作为买入价格，到6的时候价格比5高我们卖出股票，这个过程的利润就可以看成(5-1)+(6-5)，也就是6-1。所以我们只需把每天的正利润累加起来即可得到正确答案。代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int res = 0;
        for(int i = 1;i <n;i++){
            res += Math.max(prices[i]-prices[i-1],0);
        }
        return res;
    }
}

买卖股票的最佳时机 III

题目链接：买卖股票的最佳时机 III

描述：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

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

输入：prices = [3,3,5,0,0,3,1,4]
输出：6

​ 这道题跟股票II相比区别在于这里限制了交易次数是最多两次，也就是我们不能像股票II那样去贪心了，那就使用动态规划的做法来写。因为限制交易次数，状态可以分为：不操作、第一次交易买入、第一次交易卖出、第二次交易买入和第二次交易卖出这五种状态。用二维数组表示的话就是dp[n][5]，其中dp[i][0]代表不操作，dp[i][1]代表在第i天第一次交易中是有买入股票，但要注意不一定是在第i天买的，dp[i][2]代表在第i天第一次交易已卖出，也要注意不一定是在第i天卖出。dp[i][3]和dp[i][4]的意思也跟上面一样，区别在于是代表第二次交易，dp[i][3]的更新会需要有dp[i-1][2]的参与，因为这次的买入后利润是要基于第一次交易完成后的利润来计算的。代码就如下：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for(int i = 1;i < n;i++){
            dp[i][0] = dp[i-1][0];
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-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[n-1][4];
    }
}

通过代码可以看到dp[i]的状态只依赖于dp[i-1]，那么可以考虑缩减层次，这里可以用四个常量来表示后四种状态，代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        //fb表示该天第一次买入股票的最大利润，fs表示该天第一次卖出股票的最大利润
        int fb = -prices[0],fs = 0;
        //sb表示该天第二次买入股票的最大利润，ss表示该天第二次卖出股票的最大利润
        int sb = -prices[0],ss = 0;
        for(int i = 1;i < prices.length;i++){
            int p = prices[i];
            fb = Math.max(-p,fb);
            fs = Math.max(fs,fb+p);
            sb = Math.max(sb,fs-p);
            ss = Math.max(ss,p+sb);
        }
        return ss;
    }
}

买卖股票的最佳时机 IV

题目链接：买卖股票的最佳时机 IV

描述：

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

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

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7

​ 这题其实跟股票III差不多的，只不过最多交易次数从2变成了k这个不定量，思维还是相通的，通过列举k为2、3、4可以发现，在dp[i][j]中第二维的下标为奇数时都是代表股票买入的状态，下标为偶数(除了0)都是代表股票卖出的状态。于是我们的二维数组就可以申请为dp[n][2*k+1]。这里有一个思考点，就是k如果大于等于数组长度的一般的话，其实就变成跟股票II一样的题目没有限制最多交易次数了，因为买入卖出才算一次交易，也就是一次交易就占据了两天，如果最多次数超过数组长度的一半，那也就是相当于超过n天了，所以在k大于等于数组长度一半时直接采用贪心做法更加高效。代码如下：

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(0 == k || n == 0)return 0;
        //当交易次数的限制超过或等于数组长度一半时等同于无限制
        if(k >= n/2)return greedy(prices);
        int[][] dp = new int[n][2*k+1];
        for(int i = 1;i < 2*k;i+=2){
            dp[0][i] = -prices[0];
        }
        for(int i = 1;i < n;i++){
            for(int j = 0;j < 2*k-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[n-1][2*k];
    }

    public int greedy(int[] prices){
        int max = 0;
        for(int i = 1;i < prices.length;i++){
            max += Math.max(prices[i]-prices[i-1],0);
        }
        return max;
    }
}

跟上一题一样，也可以考虑对二维数组进行优化。这里的优化采用了两个一维数组buy[k+1]和sell[k+1]来代表在第i笔交易时买入股票和卖出股票时的最大利润，buy[i]的更新会参考上一笔交易卖出后的利润，所以容易得出buy的转移方程为buy[i] = max(buy[i],sell[i-1]-prices[j])，而sell的更新很容易因为我们常规套路做多的思维而写成sell[i] = max(sell[i],buy[i-1]+prices[j])，但要本次卖出股票只有在本次交易买入后才能卖出，而不能参考上一次买入股票时的利润，在执行本次卖出时上一次的交易已经是完成的了，所以是buy[i]+prices[j]。代码如下：

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(0 == k || n == 0)return 0;
        //当交易次数的限制超过或等于数组长度一半时等同于无限制
        if(k >= n/2)return greedy(prices);
        //第i笔交易买入股票时的最大利润
        int[] buy = new int[k+1];
        //第i笔交易卖出股票时的最大利润
        int[] sell = new int[k+1];
        Arrays.fill(buy,-prices[0]);
        //写成for(int j = 0;j < n;j++)的形式当成天数会比较好理解
        for(int p : prices){
            for(int i = 1;i <= k;i++){
                //比较本次交易不买入股票的利益和上一笔交易卖出后买入股票的利益谁大
                buy[i] = Math.max(buy[i],sell[i-1]-p);
                //比较本次交易不卖出股票的利益和本次交易卖出股票的利益谁大
                sell[i] = Math.max(sell[i],buy[i]+p);
            }
        }
        return sell[k];
    }

    public int greedy(int[] prices){
        int max = 0;
        for(int i = 1;i < prices.length;i++){
            max += Math.max(prices[i]-prices[i-1],0);
        }
        return max;
    }
}

以上就是买卖股票四题的方法总结了。

参考

• 代码随想录——股票三
• 代码随想录——股票四
• 力扣题解及评论区