题目链接：121. 买卖股票的最佳时机

题解：

简单的贪心问题！

题目简述：

给定一个序列，从中选择两点（保证：后者大于前者），求其最大值作为股票的最大利润！

题解：

贪心： res表示0 ~ i区间的最大股票收益，minv表示该区间的最小值。

求最大值，则当前区间的最小值和当前区间的最后一个值的差自然就是该区间的最大股票收益了，遍历一遍该数组即可得到最大股票收益！

  • 得到1 ~ i - 1的最小值minv
  • 做差即可：price[i] - minv

时间复杂度：O(n)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0, minv = INT_MAX;
        for(int i = 0; i < prices.size(); i++){
            res = max(res, prices[i] - minv);
            minv = min(minv, prices[i]);
        }
        return res;
    }
};