仅以此记录所学所想,如有错误,还望指正。
首次尝试
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、感觉自己无法独立想出这种好方法啊,急需解决。