买股票的最佳时机（121）

题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例

输入: [7,1,5,3,6,4] 输出: 5

输入: [7,6,4,3,1] 输出: 0

算法

暴力法

function maxProfit(prices) {
  let profit = 0
  for(let i = 0; i < prices.length - 1; i++) {
    for(let j = i + 1; j < prices.length; j++) {
      if (prices[j] - prices[i] > profit) {
        profit = prices[j] - prices[i]
      }
    }
  }
  return profit
}

贪心算法

双窗口+滑动指针实现贪心算法，左指针表示买入时间（[0, length-1]），右指针表示卖出时间（[1, length]）。每次循环滑动右指针，若右指针小于左指针（此时不可能卖出）则将左指针指向右指针当前位置并且让右指针+1；若右指针大于左指针（则可以卖出）则判断当前利润是否大于已获得的利润，如果大于则卖出，否则跳过，然后让右指针+1并且左指针不变

function maxProfit(prices) {
  let i = 0, j = 0, profit = 0
  while(j < prices.length) {
    if (prices[i] > prices[j]) {
      prices[i] = prices[j]
      i = j
      j = i + 1
    } else {
      if (prices[j] - prices[i] > profit) {
        profit = prices[j] - prices[i]
      }
      j++
    }
  }
  return profit
}

另一个贪心算法

function maxProfit(prices) {
  let profit = 0, min = prices[0]
  for(let i = 1; i < prices.length; i++) {
    if (prices[i] < min) {
      min = prices[i]
    } else {
      if(prices[i] - min > profit) {
        profit = prices[i] - min
      }
    }
  }
  return profit
}