121. 买卖股票的最佳时机

解题思路

题目要求只能在某一天买，之后的某天卖，利润 = 卖的价格 - 买的价格，让卖的价格最高，买的价格最低，则利润最大，且附加限制条件：先买后卖；

以这样的顺序迭代：

  1. 第一天买入，第二天卖出；
  2. 前两天的某天以最低价买入，第三天卖出；
  3. 前三天的某天以最低价买入，第四天卖出；
  4. …

细节：

  • 可见每次迭代需要计算当天以前（不包含当天）的最低价格，可以用变量min记忆并逐步更新最低价；
  • 最润终需要返回最大利，由于利润每次迭代都要计算，可用变量profit记忆并逐步更新最大利润；
  • 由于第i天卖出时参与计算的是前i-1天的最低价格，递推一下：min初始化为第一天价格，从第二天开始卖出；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    // min表示最低买入价
    let min = prices[0];
    // profit表示利润，默认为0
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        profit = Math.max(profit, prices[i] - min);
        min = Math.min(min, prices[i]);
    }

    return profit;
};