剑指Offer题解 - Day18

「剑指 Offer 63. 股票的最大利润」

力扣题目链接[1]

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 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。

「限制：」

0 <= 数组长度 <= 10^5

思路：

假如采用暴力法求解，那么根据题目描述，可以得出交易方案数一共有：

(n−1)+(n−2)+⋯+2+1=n(n−1)/2 种，时间复杂度为O(n^2) ，因此该方法不考虑。

本题可应采用动态规划的方式进行求解。首先，需要归纳出动态规划的方程。可以得出以下结论：

• 假设f(n)代表前n日的最大利润。
• f(0) = 0，也就是说首天的利润是0。
• 那么，f(n)就等于前n - 1日的利润和第n日卖出利润的最大值。
• f(n) = max(f(n - 1), (prices[n] - min([0, n))))

解释一下动态规划方程：

前n日的最大利润，就是比较前n - 1日的利润，第n日的卖出利润的最大值。而第n日的卖出利润就是当天的股票价格减去前面n天的最低价格。

根据以上分析，可以得出以下代码：

动态规划

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let max = 0;
    for (let i = 0; i < prices.length; i++) {
        max = Math.max(max, (prices[i] - Math.min(...prices.slice(0,i))))
    }
    return max;
};

• 「时间复杂度 O(n^2)」。
• 「空间复杂度 O(1)」。

分析：

通过代码实现出动态规划方程，在力扣里执行代码并提交是可以通过的，但是效率特别的低。会发现比较耗时的代码是计算前 n 天的最小值，时间复杂度是O(n)。而外层嵌套有循环，因此降低了执行效率。

所以，我们需要通过维护额外的变量进行统计前n天的最小值，而不要每次都动态计算。

动态规划优化

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let value = 0;
    let price = +Infinity; // 初始化无穷大，方便后续比较较小值
    for (let i = 0; i < prices.length; i++) {
        price = Math.min(price, prices[i]); // 将上次比较的最小值与当前值比较，获取最新最小值
        value = Math.max(value, (prices[i] - price)) // 动态规划方程
    }
    return value;
};

• 「时间复杂度 O(n)」。
• 「空间复杂度 O(1)」。

分析：

我们动态的缓存最新的最小值，避免了每次取prices[i]以前所有的值进行比较。如此优化，可以将时间复杂度降低至O(n) 。

总结

本题的难点在于动态规划方程的归纳，以及动态的缓存最小值。

可以得出一个通用的法则：当需要获取最小值时，初始化的变量赋值为+Infinity ，方便比较出最小值；反过来的话，就需要将初始化的变量赋值为-Infinity ，方便比较出最大值。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58nn7r/