490，动态规划和双指针解买卖股票的最佳时机

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

We do not remember days, we remember moments.

我们往往记住的不是某一天，而是某个时刻。

问题描述

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

动态规划解决

这题是让求完成一笔交易所获得的最大利润，首先我们来看一下使用动态规划该怎么解决，动态规划还是那常见的几个步骤

确定状态
找到转移公式
确定初始条件以及边界条件
计算结果

我们来定义一个二维数组dp[length][2]，其中dp[i][0]表示第i+1天（i是从0开始的）结束的时候没持有股票的最大利润，dp[i][1]表示第i+1天结束的时候持有股票的最大利润。

如果我们要求第i+1天结束的时候没持有股票的最大利润dp[i][0]，那么会有两种情况。

第一种情况就是第i+1天我们即没买也没卖，那么最大利润就是第i天没持有股票的最大利润dp[i-1][0]。

第二种情况就是第i+1天我们卖了一支股票，那么最大利润就是第i天持有股票的最大利润（这个是负的，并且也不一定是第i天开始持有的，有可能在第i天之前就已经持有了）加上第i+1天卖出股票的最大利润，dp[i-1][1]+prices[i]。

很明显我们可以得出

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);

同理我们可以得出第i+1天结束的时候我们持有股票的最大利润

dp[i][1]=max(dp[i-1][1],-prices[i])；

边界条件就是第1天的时候，如果我们不持有股票，那么

dp[0][0]=0;

如果持有股票，那么

dp[0][1]=-prices[0];

有了边界条件和递推公式，代码就很容易写出来了，来看下代码

 1public int maxProfit(int[] prices) {
 2    if (prices == null || prices.length == 0)
 3        return 0;
 4    int length = prices.length;
 5    int[][] dp = new int[length][2];
 6    //边界条件
 7    dp[0][0]= 0;
 8    dp[0][1] = -prices[0];
 9    for (int i = 1; i < length; i++) {
10        //递推公式
11        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
12        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
13    }
14    //毋庸置疑，最后肯定是手里没持有股票利润才会最大，也就是卖出去了
15    return dp[length - 1][0];
16}

代码优化

我们看到上面二维数组中计算当天的最大利润只和前一天的利润有关，所以没必要使用二维数组，只需要使用两个变量即可，一个表示当天持有股票的最大利润，一个表示当天没持有股票的最大利润，代码如下。

 1public int maxProfit(int[] prices) {
 2    if (prices == null || prices.length == 0)
 3        return 0;
 4    int length = prices.length;
 5    int hold = -prices[0];//持有股票
 6    int noHold = 0;//不持有股票
 7    for (int i = 1; i < length; i++) {
 8        //递推公式
 9        noHold = Math.max(noHold, hold + prices[i]);
10        hold = Math.max(hold, -prices[i]);
11    }
12    //毋庸置疑，最后肯定是手里没持有股票利润才会最大，
13    //也就是卖出去了
14    return noHold;
15}

双指针解决

我们还可以使用两个指针，一个指针记录访问过的最小值（注意这里是访问过的最小值），一个指针一直往后走，然后计算他们的差值，保存最大的即可，这里就以示例1为例来画个图看下

原理比较简单，来看下代码

 1public static int maxProfit(int[] prices) {
 2    if (prices == null || prices.length == 0)
 3        return 0;
 4    int maxPro = 0;//记录最大利润
 5    int min = prices[0];//记录数组中访问过的最小值
 6    for (int i = 1; i < prices.length; i++) {
 7        min = Math.min(min, prices[i]);
 8        maxPro = Math.max(prices[i] - min, maxPro);
 9    }
10    return maxPro;
11}

单调栈解决

单调栈解决的原理很简单，我们要始终保持栈顶元素是所访问过的元素中最小的，如果当前元素小于栈顶元素，就让栈顶元素出栈，让当前元素入栈。如果访问的元素大于栈顶元素，就要计算他和栈顶元素的差值，我们记录最大的即可，代码如下。

 1public int maxProfit(int[] prices) {
 2    if (prices == null || prices.length == 0)
 3        return 0;
 4    Stack<Integer> stack = new Stack<>();
 5    stack.push(prices[0]);
 6    int max = 0;
 7    for (int i = 1; i < prices.length; i++) {
 8        //如果栈顶元素大于prices[i]，那么栈顶元素出栈，
 9        //把prices[i]压栈，要始终保证栈顶元素是最小的
10        if (stack.peek() > prices[i]) {
11            stack.pop();
12            stack.push(prices[i]);
13        } else {
14            //否则如果栈顶元素不大于prices[i]，就要计算
15            //prices[i]和栈顶元素的差值
16            max = Math.max(max, prices[i] - stack.peek());
17        }
18    }
19    return max;
20}

仔细看下就会明白这种解法其实就是双指针的另一种实现方式，只不过双指针使用的是一个变量记录访问过的最小值，而这里使用的是栈记录的。

参照最大子序和

在前面刚讲过最大子序和的问题，不明白的可以看下486，动态规划解最大子序和，今天这题完全可以参照第486的解题思路。

假设数组的值是[a,b,c,d,e,f]，我们用数组的前一个值减去后一个值，得到的新数组如下

[b-a,c-b,d-c,e-d,f-e]

我们在新数组中随便找几个连续的数字相加就会发现一个规律，就是中间的数字都可以约掉，比如新数组中第1个到第4个数字的和是

b-a+c-b+d-c+e-d=e-a。

我们来看下示例1中得到的新数组，连续的最大值就是

4+(-2)+3=5。

搞懂了上面的原理代码就简单多了，我们前面刚讲的最大子序和的代码如下

 1public int maxSubArray(int[] num) {
 2    int length = num.length;
 3    int cur = num[0];
 4    int max = cur;
 5    for (int i = 1; i < length; i++) {
 6        cur = Math.max(cur, 0) + num[i];
 7        //记录最大值
 8        max = Math.max(max, cur);
 9    }
10    return max;
11}

然后我们来对他进行修改一下，就是今天这题的答案了。

 1public int maxProfit(int[] prices) {
 2    if (prices == null || prices.length == 0)
 3        return 0;
 4    int length = prices.length;
 5    int cur = 0;
 6    int max = cur;
 7    for (int i = 1; i < length; i++) {
 8        //这地方把prices[i]改为 prices[i] - prices[i - 1]即可
 9        cur = Math.max(cur, 0) + prices[i] - prices[i - 1];
10        //记录最大值
11        max = Math.max(max, cur);
12    }
13    return max;
14}

暴力解决

这种是两两比较，保存计算的最大值即可，没啥可说的，虽然简单，但效率很差，看下代码

 1public int maxProfit(int[] prices) {
 2    if (prices == null || prices.length == 0)
 3        return 0;
 4    int maxPro = 0;
 5    for (int i = 0; i < prices.length; i++) {
 6        for (int j = i + 1; j < prices.length; j++) {
 7            maxPro = Math.max(maxPro, prices[j] - prices[i]);
 8        }
 9    }
10    return maxPro;
11}