likes
comments
collection
share

LeetCode 122：买卖股票的最佳时机 II

作者站长头像
站长
· 阅读数 103

买卖股票的最佳时机 II

题目描述

给你一个整数数组 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 。

解题思路

思路一：遍历找波峰波谷

找到最小值波谷， 最大值波峰，差值即是利润 LeetCode 122：买卖股票的最佳时机 II 实现代码如下：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let profix = 0, valley = prices[0], peak = prices[0], i = 0, len = prices.length;
    while (i < len - 1) {
        // 也是需要注意i要小于len - 1
        while (i < len - 1 && prices[i] >= prices[i + 1]) {
            i++;
        }
        valley = prices[i];
        while (i < len - 1 && prices[i] <= prices[i + 1]) {
            i++;
        }
        peak = prices[i];
        profix += peak - valley;
    }
    return profix;
};

思路二：贪心算法（针对这道题的特殊算法）

由于不限制交易次数，只要今天股价比昨天高，就交易。 该算法仅可以用于计算，但 计算的过程并不是真正交易的过程 如： [1, 2, 3, 4, 5],数组的长度 n=5 ，由于对所有的 1≤i<n 都有 prices[i]>prices[i-1]，因此答案为

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

但是实际的交易过程并不是进行 4 次买入和 4 次卖出，而是在第 1 天买入，第 5 天卖出。

这道题 贪心 的地方在于，对于 「今天的股价 - 昨天的股价」，得到的结果有 3 种可能：① 正数，② 0，③负数。贪心算法的决策是： 只加正数 。 实现代码如下：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxprofix = 0;
    let len = prices.length;
    for (let i = 1; i < len; ++i) {
        let tmp = prices[i] - prices[i - 1];
        tmp > 0 && (maxprofix += tmp); 
    }
    return maxprofix;
};

  • 时间复杂度：O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。

  • 空间复杂度：O(1)。只需要常数空间

思路三： 动态规划

第 1 步：定义状态 状态 dp[i][j] 定义如下：

dp[i][j] 表示到下标为 i 的这一天，持股状态为 j 时，我们手上拥有的最大现金数。

其中：

第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）(i从0开始)； 第二维 j 表示下标为 i 的那一天是持有股票（即没有交易），还是持有现金（即交易了）。这里 0 表示持有现金，1 表示持有股票。

第 2 步：状态转移方程

考虑 dp[i][0] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即 dp[i−1][1]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程

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

同理： dp[i][1] 的转移方程如下：

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

第 3 步：确定初始值 起始的时候：

如果什么都不做，dp[0][0] = 0； 如果持有股票，当前拥有的现金数是当天股价的相反数，即 dp[0][1] = -prices[i]；

第 4 步：确定输出值 输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][1]。即持有股票的收益一定低于不持有股票的收益

实现代码如下：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const len = prices.length; 
    const dp = Array.from(Array(len), () => new Array(2));
    dp[0][0] = 0, dp[0][1] = -prices[0];
    for (let 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], dp[i - 1][0] - prices[i]);
    }
    return dp[len - 1][0];
};

  • 时间复杂度：O(n)，其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。

  • 空间复杂度：O(n)。需要O(n) 空间存储动态规划中的所有状态。

优化 只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量 优化后代码如下：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const len = prices.length;
    let dp0 = 0, dp1 = -prices[0];
    for (let i = 1; i < len; ++i) {
        let newDp0 = Math.max(dp0, dp1 + prices[i]);
        let newDp1 = Math.max(dp1, dp0 - prices[i]);
        dp0 = newDp0;
        dp1 = newDp1;
    }
    return dp0;
};
  • 空间复杂度：O(1)

参考资料

LeetCode.122 - 买卖股票的最佳时机 II - 力扣（LeetCode）

转载自:https://juejin.cn/post/7150893816231231495
评论
请登录