题目名称：买卖股票的最佳时机

题目地址: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

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

解法

1. 暴力解

  • 可以采用暴力解法，从第一天开始买，记录之后所有天卖出的结果中最大值；依次记录第二天，第三天……第n天买到最后一天卖出的最大值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /**
     * @param {number[]} prices
     * @return {number}
     */
    var maxProfit = function (prices) {
      if (!prices || !prices.length) return 0
      const len = prices.length
      let max = 0,
        cur = 0,
        next = 0
      for (let i = 0; i < len; i++) {
        cur = prices[i]
        for (let j = i + 1; j < len; j++) {
          next = prices[j]
          if (cur < next) {
            max = Math.max(max, next - cur)
          }
        }
      }
      return max
    }

2. 最低价格递推法

  • 由于先买后卖，依次向后推进过程中，只需要跟踪最小值和最大差值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit1 = function (prices) {
  if (!prices || !prices.length) return 0
  let min = prices[0] // 最小值
  let res = 0 // 最大差值
  for (let i = 0; i < prices.length; i++) {
    min = Math.min(min, prices[i])
    res = Math.max(res, prices[i] - min)
  }
  return res
}

结合代码查看基本原理：

如何能保证这个思考方式有效？

  • 极限情况：后面出现了min值更小的情况

根据推算发现，即使后面出现min值更小的情况，仍然能保证第二天买第三天卖获利最高，因为max在单次循环中得到了保留

测试用例

1
2
3
4
5
6
7
8
9
10
11

// 测试用例
let test = [7, 1, 5, 3, 6, 4]
let test1 = [7, 6, 4, 3, 1]

console.time("执行用时")
console.log(maxProfit(test))
console.log(maxProfit(test1))
console.log(maxProfit1(test))
console.log(maxProfit1(test1))
console.timeEnd("执行用时")

总结

  • 单次循环，跟踪最小值和最大差值即可

说明

  1. 本题解已同步GitHub地址，可以复制代码进行调试。
  2. 总结出了一套亲测有效的前端无痛刷题项目，有助于算法小白平稳入门，详见leetcode-js-roadmap，希望对从零开始刷题的前端小伙伴们带来帮助~