「力扣」第 121 题：买卖股票的最佳时机（简单）

「力扣」第 121 题：买卖股票的最佳时机（简单）

• 链接
• 题解链接

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

方法一：暴力枚举

使用两个变量 i 和 j ，它们分别表示买进这支股票和卖出这支股票，枚举它们在价格数组上可能出现的所有位置。编码很简单，相信大家都会，写一个二重循环即可。

参考代码 1：

public class Solution {

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

        // 有可能不做交易，因此结果的初始值设置为 0 
        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                res = Math.max(res, prices[j] - prices[i]);
            }
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：$O(N^2)$，这里 $N$ 是股价数组的长度；
• 空间复杂度：$O(1)$

复杂度较高，提交到 LeetCode 以后排名稍微靠后。

方法二：针对暴力枚举的优化

我们发现：其实只需要关心之前（不包括现在）看到的最低股价，于是在遍历的过程中，记录下之前看到的最低股价，就可以省去内层循环。

参考代码 2：

public class Solution {

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

        int res = 0;

        // 表示在当前位置之前的最小值，假设修正法（打擂台法）
        int minVal = prices[0];
        // 注意：这里从 1 开始
        for (int i = 1; i < len; i++) {
            res = Math.max(res, prices[i] - minVal);
            minVal = Math.min(minVal, prices[i]);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(1)$。

方法三：动态规划

动态规划的 5 个步骤：

1、设定状态

这道题其实是一个典型的二维 dp 问题。“动态规划”用于多阶段最优化问题的求解。这里天数代表每个阶段，即一天一天看，设置为第一维。为了消除后效性（前面的状态确定下来以后不会因为后面状态而更改），将当天是否持股设置为第二维的状态。于是：

状态 dp[i][j] 表示：在索引为 i 的这一天，用户手上持股状态为 j 所获得的最大利润。

说明：

1. j 只有 2 个值：0 表示不持股（特指卖出股票以后的不持股状态），1 表示持股。
2. “用户手上不持股”不代表用户一定在索引为 i 的这一天把股票抛售了；

2、思考状态转移方程

dp[i][0] 怎样转移？

• dp[i - 1][0] ：当然可以从昨天不持股转移过来，表示从昨天到今天什么都不操作，这一点是显然的；

• dp[i - 1][1] + prices[i]：昨天持股，就在索引为 i 的这一天，我卖出了股票，状态由 1 变成了 0，此时卖出股票，因此加上这一天的股价。

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

dp[i][1] 怎样转移？

• dp[i - 1][1] ：昨天持股，今天什么都不操作，当然可以从昨天持股转移过来，这一点是显然的；

• -prices[i]：注意：状态 1 不能由状态 0 来，因为事实上，状态 0 特指：“卖出股票以后不持有股票的状态”，请注意这个状态和“没有进行过任何一次交易的不持有股票的状态”的区别。

因此，-prices[i] 就表示，在索引为 i 的这一天，执行买入操作得到的收益。注意：因为题目只允许一次交易，因此不能加上 dp[i - 1][0]。

综上：dp[i][1] = max(dp[i - 1][1], -prices[i]);

3、考虑初始值

• 第 0 天不持股，显然 dp[0][0] = 0；

• 第 0 天持股，显然dp[0][1] = -prices[0]。

4、考虑输出

从状态转移方程可以看出，每一天的状态都考虑了之前的状态。在只发生一次交易的情况下，持有这支股票一定不能使我们获得最大利润。因此输出是 dp[len - 1][0]，不可能是持股的状态 dp[len - 1][1]，

参考代码 3：

Java 代码：

public class Solution {

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

        // 0：用户手上不持股所能获得的最大利润，特指卖出股票以后的不持股，非指没有进行过任何交易的不持股
        // 1：用户手上持股所能获得的最大利润

        // 注意：因为题目限制只能交易一次，因此状态只可能从 1 到 0，不可能从 0 到 1
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; 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[len - 1][0];
    }
}

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(N)$。

说明：如果我们一定要区分“不持有股票”的状态是“一开始不持有”和“卖出股票以后的不持有”，设置 3 个状态即可，我个人认为更加清晰。

下面状态的设置和状态转移方程均写在代码注释中：

参考代码 4：

Java 代码：

public class Solution {

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

        // 0：不进行任何操作
        // 1：用户执行了一次买入操作
        // 2：用户执行了一次卖出操作

        // 状态转移方程：
        // dp[i][0] 永远等于 0
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        // dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])


        // 注意：如果是 `[7, 6, 5, 4, 3]` 这种波动，应该不交易，
        // 因此输出是：max(dp[len - 1][0], dp[len - 1][2])

        int[][] dp = new int[len][3];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        // 这里状态 2 不应该有值，设置为 0 不影响正确性
        dp[0][2] = 0;
        for (int i = 1; i < len; i++) {
            // 可以不显式赋值，因为 int 的初值就是 0
            dp[i][0] = 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]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][2]);
    }
}

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(N)$。

说明：事实上，这一版代码，由于 dp[i][0] = 0 恒成立，和“参考代码 3”其实是等价的。

5、考虑是否可以状态压缩

由于 dp[i] 仅仅依赖于 dp[i - 1] ，因此，我们可以使用滚动数组的技巧压缩变量。下面根据“参考代码 3”进行修改：

参考代码 5：

public class Solution {

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

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

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(1)$，状态压缩以后相当于只用了 $4$ 个变量。

我们继续观察“参考代码 3”，因为状态只能从 1 到 0，即先有状态 1 再有状态 0，我们在填写“状态表 dp” 的时候，只需要用 1 维，因此填表的时候，先写 0 再写 1 即可。

参考代码 6：（根据“参考代码 3”进行修改）

public class Solution {

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

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

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(1)$，状态压缩以后相当于只用了 $2$ 个变量。

很有意思的是，可以将此时的数组 dp 语义化，dp[1] = Math.max(dp[1], -prices[i]); 等价于 dp[1] = Math.min(dp[1], prices[i]); 其实就是“参考代码 2” 中的 minVal，dp[0] 等价于 “参考代码 2” 中的 res。

方法四：使用差分数组（参考）

因为我们关注股票的变化，因此明天减去今天的差价在一定程度上是有研究价值的。我们使用数组 diff 表示差分数组。

说明：差分 diff 是 difference 的缩写。

差分数组是这样得到的：

int[] diff = new int[len - 1];
for (int i = 0; i < len - 1; i++) {
    diff[i] = prices[i + 1] - prices[i];
}

那么：

diff[2] + diff[1] = prices[3] - prices[2] + (prices[2] - prices[1]) =  prices[3] - prices[1]

我们再多写几个：

diff[3] + diff[2] + diff[1] = (diff[4] - diff[3]) + (prices[3] - prices[2]) + (prices[2] - prices[1]) =  prices[4] - prices[1]

我们发现：差分数组的连续子区间和的值，就正好是原始股价数组进行一次交易的差价（后 - 前）。因此，我们可以在差分数组上，求“最大连续子序列的和”，这里参考了「力扣」第 53 题：“最大子序和” 的做法。

参考代码 7：

public class Solution {

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

        // 差分数组比原始数组的长度少 1
        int[] diff = new int[len - 1];
        for (int i = 0; i < len - 1; i++) {
            diff[i] = prices[i + 1] - prices[i];
        }

        // dp[i] 以 diff[i] 结尾的子序列的和的最大值
        int[] dp = new int[len - 1];
        dp[0] = diff[0];
        for (int i = 1; i < len - 1; i++) {
            dp[i] = Math.max(diff[i], dp[i - 1] + diff[i]);
        }

        // 还是要考虑到 [7 , 6, 5, 4, 3] 这种不交易的情况
        // 初值应该赋值成 0
        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(N)$。

根据“最大子序和”对于状态空间的压缩优化，可以写出下面的代码。

参考代码 8：

说明：下面把数组 diff 也压缩了，大家编码的时候要极其小心。

1、数组 diff 与状态数组的索引对应关系要清楚；

2、 int res = Math.max(0, pre); 这行代码我是在提交测评以后才想到的，应该把不交易的情况考虑进去。

个人认为状态压缩以后的代码，虽然空间复杂度较优，但是编码晦涩难懂，容易编写出错，不易维护，个人不推荐在工作中写这样的代码。

public class Solution {

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

        int pre = prices[1] - prices[0];
        // 还是要考虑到 [7 , 6, 5, 4, 3] 这种不交易的情况
        // 初值应该考虑 0
        int res = Math.max(0, pre);
        int diff;
        int cur;

        for (int i = 1; i < len - 1; i++) {
            diff = prices[i + 1] - prices[i];
            cur = Math.max(diff, pre + diff);
            res = Math.max(res, cur);
            pre = cur;
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：$O(N)$；
• 空间复杂度：$O(1)$，状态压缩以后只使用了常数个变量，与问题的规模无关。