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

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

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

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

动态规划解法

思路

我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

在一次遍历中找到价格的最小值和以每一位作为售价时的利润，如果在此位置售出时可以获得最高利润则更新最高利润，最终返回保存的最高利润即可。

保存历史最小价格和到此刻为止可获得的最大利润（历史上的高价减最低价格）。

复杂度

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

代码

var maxProfit = function (prices) {
  if (!prices.length) {
    return 0;
  }
  let minPrice = prices[0];
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    let item = prices[i];
    minPrice = Math.min(minPrice, item);
    if (item - minPrice > maxProfit) {
      maxProfit = item - minPrice;
    }
  }
  return maxProfit;
};
let result = maxProfit([7, 1, 5, 3, 6, 4]);
console.log(result);