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

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

求最值的问题我们用动态规划是比较容易想到答案的，设dp[i]为第i天卖出股票时的最大利润。

由于题目要求我们只能进行一次交易，当希望在第i天卖出时，那么买入的时间点一定是在此之前的最低点才行。因此我们还需要一个变量存入在第i天以前的价格最低点min。

状态转移方程：dp[i] = nums[i] - min

得到了状态转移方程，我们很明显可以看出，dp[i]与dp[?]之间并没有直接关系，因此我们只需要一个变量存入dp[i]中的最大值就能得出答案了，从而节省了空间复杂度。

function maxProfit(prices: number[]): number {
  const len = prices.length;
  let res = 0;
  let min = prices[0];

  for (let i = 1; i < len; i++) {
    res = Math.max(res, prices[i] - min);
    min = Math.min(min, prices[i]);
  }

  return res;
}