top面试121.买卖股票的最佳时机

题目描述:

top面试121.买卖股票的最佳时机

思路:暴力法比较简单,但提交会超时。假设在第i天卖出,我们需要知道前i天的最小值,使用一次遍历,更新最大值即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        //前i天的最小价格
        int min_price=INT_MAX;
        //第i天卖出的最大利润
        int max_profit=0;
        for(int i=0;i<n;i++){
            //更新最小价格
            if(prices[i]<min_price)
                min_price=prices[i];
            //更新最大利润
            else if(prices[i]-min_price>max_profit)
                max_profit=prices[i]-min_price;
        }
        return max_profit;
    }
};

 

猜你喜欢