1 题目

121-买卖股票的最佳时机

2 思路

遍历数组，维护一个当前股票的最低价格 min_price，维护一个当前最高收益 max_profit。如果当前遍历的值大于 min_price，则更新min_price；如果当前遍历的值减去min_price得到的收益，大于max_profit，则更新max_profit。

整体思路还是很简单和清晰的，维护当前股票价格最低值和当前最大收益即可，这样不断更新就能得到最终的 max_profit。

时间复杂度：O(n)，空间复杂度：O(1)。

3 题解

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int min_price = prices[0];
    int max_profit = 0;

    for (int i = 0; i < prices.size(); ++i) {
      int delta = prices[i] - min_price;
      if (delta <= 0) {
        min_price = prices[i];
        continue;
      }
      max_profit = max_profit > delta ? max_profit : delta;
    }

    return max_profit;
  }
};

看一眼官方题解，还是更优雅一些，学习学习：

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int min_price = prices[0], max_profit = 0;
    for (int price : prices) {
      max_profit = max(max_profit, price - min_price);
      min_price = min(price, min_price);
    }
    return max_profit;
  }
};