买卖股票的最佳时机

Tips

题目类型: Dynamic Programming, Greedy

相关题目:

• 122. 买卖股票的最佳时机-ii
• 123. 买卖股票的最佳时机-iii
• 188. 买卖股票的最佳时机-iv
• 309. 最佳买卖股票时机含冷冻期
• 714. 买卖股票的最佳时机含手续费

题目

给定一个数组 prices, 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格.

你只能选择某一天买入这只股票, 并选择在未来的某一个不同的日子卖出该股票. 设计一个算法来计算你所能获取的最大利润.

返回你可以从这笔交易中获取的最大利润. 如果你不能获取任何利润, 返回 0.

提示:

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁴
• s 中至少存在一个单词

示例

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

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

题解

JavaScript - 贪心

该题最简单的办法是用贪心, 即选取最低点买入, 再之后选择一个高点卖出.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let min = Number.MAX_SAFE_INTEGER
  let max = 0

  for (let i = 0; i < prices.length; i++) {
    min = Math.min(min, prices[i])
    max = Math.max(max, prices[i] - min)
  }

  return max
}

JavaScript - 动态规划

对于某一天 i, 要么是持有, 要么是不持有.

如果是持有:

• 这一天买入, 因为只能买一次, 所以跟之前状态无关, 那么: dp[i][0] = -prices[i]
• 如果之前已经买入了, 那么: dp[i][0] = dp[i - 1][0]

如果是不持有:

• 这一天卖出, 那么: dp[i][1] = dp[i - 1][0] + prices[i]
• 之前已经卖出了, 那么: dp[i][1] = dp[i - 1][1]

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const n = prices.length
  const dp = new Array(n).fill(0).map(() => new Array(2).fill(0))

  dp[0][0] = -prices[0] // 第 0 天买入, 现金余额就是 -prices[0]
  dp[0][1] = 0 // 第 0 天卖出, 现金余额就是 0
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(-prices[i], dp[i - 1][0])
    dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1])
  }

  return dp[n - 1][1]
}