[leetcode]121.买卖股票的最佳时机

[MagicalBridge]

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

解决方案

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

形式上，对于每组 i 和 j (其中 j > i) 我们需要找出 max(prices[j] - prices[i]);

方法一: 暴力法

/**
 * @param {number[]} prices
 * @return {number}
 */
// 第一种解法,使用两个变量 i 和 j 他们分别表示买进这支股票和卖出这支股票的价格
// 枚举它们在价格数组上可能出现的所有位置，算出价格差
var maxProfit = function (prices) {
  let len = prices.length;
  if (len < 2) {
    return 0;
  }
  // 有可能不做交易，所以初始值为0
  let res = 0;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      res = Math.max(res, prices[j] - prices[i]);
    }
  }
  return res;
};

复杂度分析

• 时间复杂度:O(N^2) 这里N是股价数组的长度
• 空间复杂度:O(1)。

方法二：

这种方法只需要遍历一次数组，用一个变量记录遍历过程中的最小值，然后每次计算当前值和最小值之间的差为利润，然后每次选择较大的利润来更新，当遍历完成之后利润就是我们想要求得的结果。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let res = 0;
  let buy = Number.MAX_VALUE; // 表示最大值

  for (let price of prices) {
    buy = Math.min(buy, price);
    res = Math.max(res, price - buy);
  }
  return res;
};