【LeetCode精选TOP面试题】122-买卖股票的最佳时机2

LeetCode 原题链接

给定一个数组 prices ，其中  prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候   最多   只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。 返回 你能获得的 最大 利润  。

动态规划解法

思路

最多只能持有一支股票，从一个最低点到离他最近的一个最高点之间的值就是一次交易的利润。

复杂度

• 时间复杂度：O(n)，只需要遍历一次，n 为数组的长度。
• 空间复杂度：O(1)，只使用了常数个变量。

代码

var maxProfit = function (prices) {
  let maxProfit = 0;
  let minPrice = prices[0];
  let currentPrice = 0;
  for (let i = 1; i < prices.length; i++) {
    let price = prices[i];
    let lastPrice = prices[i - 1];
    minPrice = Math.min(minPrice, price);
    if (price < lastPrice) {
      // 重新购买
      minPrice = price;
      maxProfit += currentPrice;
      currentPrice = 0;
    } else {
      currentPrice = price - minPrice;
    }
  }
  maxProfit += currentPrice;
  return maxProfit;
};

let result = maxProfit([1, 2, 3, 4, 5]);
console.log(result);