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

题目

题解

动态规划的思想。即一次遍历，寻找两个数，一个是当前的全局最小值，一个是在当前的全局最小值后可以得到的最大差值

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //只需遍历一遍，存两个值
        //一个是数组中的最小值,即买入时机
        //一个是最小值后的最大值与最小值的差值，即最大利润
        int buy = INT_MAX,res = 0;//买入初始值设为最大，利润初始值设为0
        for(int price:prices){//遍历数组
            buy = min(buy,price);//取最低点买入
            res = max(res,price-buy);//取买入与卖出之间插值的最大值
        }
        return res;
    }
};