122. 买卖股票的最佳时机 II 🟨

题目

LeetCode 中等

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

题解

方法：贪心

时间复杂度：O(n)
空间复杂度：O(1)

❗️ 贪心算法只能用于计算最大利润，计算的过程并不一定是实际的交易过程。

function maxProfit(prices) {
  let len = prices.length
  let profit = 0
  for (let i = 0; i < len; i++) {
    if (prices[i + 1] > prices[i]) {
      profit += prices[i + 1] - prices[i]
    }

    console.log(
      '当前价格',
      prices[i],
      '下一价格',
      prices[i + 1],
      '累计利润',
      profit,
    )
  }
  return profit
}

const prices = [7, 1, 5, 3, 6, 4]
// const prices = [1, 2, 3, 4, 5]
// const prices = [7, 6, 4, 3, 1]
console.log('🌰', maxProfit(prices))

执行结果

当前价格 7 下一价格 1 累计利润 0
当前价格 1 下一价格 5 累计利润 4
当前价格 5 下一价格 3 累计利润 4
当前价格 3 下一价格 6 累计利润 7
当前价格 6 下一价格 4 累计利润 7
当前价格 4 下一价格 undefined 累计利润 7
🌰 7

方法：动态规划 DP

解题思路

对于每一天，我们都有两种状态：

手里没有股票（记为 cash）：可能是昨天就没有股票，也可能是昨天有股票但今天我卖了。
手里有股票（记为 hold）：可能是昨天就有股票，也可能是昨天没股票但今天我买了。

状态转移方程：

今天手里没股票 (cash) = Max(昨天手里没股票, 昨天有股票 + 今天股票卖掉赚的钱)
今天手里有股票 (hold) = Max(昨天手里有股票, 昨天没股票 - 今天买股票花的钱)

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

function maxProfit(prices) {
  if (prices.length === 0) return 0

  // 初始状态：第一天
  let cash = 0 // 第一天没买股票，利润为 0
  let hold = -prices[0] // 第一天买了股票，利润为负的第一天股价

  console.log(prices)
  console.log('cash', cash, 'hold', hold)

  for (let i = 1; i < prices.length; i++) {
    // 记录一下昨天的 cash，因为在算今天 hold 的时候要用到
    let prevCash = cash

    console.log('-------')
    console.log('价格', prices[i])
    console.log('cash计算', 'cash', cash, 'hold + prices[i]', hold + prices[i])
    console.log(
      'hold计算',
      'hold',
      hold,
      'prevCash - prices[i]',
      prevCash - prices[i],
    )

    // 更新今天的两个状态
    cash = Math.max(cash, hold + prices[i])
    hold = Math.max(hold, prevCash - prices[i])

    console.log('cash', cash, 'hold', hold)
  }

  // 最后一天手里没有股票时的利润一定最大
  return cash
}

const prices = [7, 1, 5, 3, 6, 4]
// const prices = [1, 2, 3, 4, 5]
// const prices = [7, 6, 4, 3, 1]
console.log('🌰', maxProfit(prices))

执行结果

[7,1,5,3,6,4]
cash 0 hold -7
-------
价格 1
cash计算 cash 0 hold + prices[i] -6
hold计算 hold -7 prevCash - prices[i] -1
cash 0 hold -1
-------
价格 5
cash计算 cash 0 hold + prices[i] 4
hold计算 hold -1 prevCash - prices[i] -5
cash 4 hold -1
-------
价格 3
cash计算 cash 4 hold + prices[i] 2
hold计算 hold -1 prevCash - prices[i] 1
cash 4 hold 1
-------
价格 6
cash计算 cash 4 hold + prices[i] 7
hold计算 hold 1 prevCash - prices[i] -2
cash 7 hold 1
-------
价格 4
cash计算 cash 7 hold + prices[i] 5
hold计算 hold 1 prevCash - prices[i] 3
cash 7 hold 3
🌰 7

本页目录