每日一题 ###121买卖股票的最佳时机

仅以此记录所学所想，如有错误，还望指正。

首次尝试

1、我小小的脑子只能想出暴力解法，结果是超时了。

class Solution {
public:int maxProfit(vector<int>& prices) {int max=0;for(int i=0;i<prices.size();i++){for(int j=i+1;j<prices.size();j++){if(prices[j]-prices[i]>max)max=prices[j]-prices[i];}}return max;}
};

我也知道肯定是两层for循环，O（n^2）的时间复杂度遭了。但是我想不明白如何只用一次遍历解决问题。思考五分钟，跑去看题解了。（下次多思考会儿）

题解

class Solution {
public:int maxProfit(vector<int>& prices) {int minprice=1e5;int maxprofit=0;for(int price:prices){maxprofit=max(maxprofit,price-minprice);minprice=min(minprice,price);}return maxprofit;}};

解题思路：

1、一次遍历+贪心，动态记录最小值和最大利润。每次都假设当天卖出，利润最大是当天价-之前最低的价格。再用这个利润和历史最高利润比较，取最大值。
2、先maxprofit,后minprice,是因为顺序倒置后，第一天就会出问题，最低价是自己，利润为0，同天买入卖出。

学习收获：

1、第一次看for(int price:prices)这种语法，之前一直没用过。
2、感觉自己无法独立想出这种好方法啊，急需解决。