欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-16 09:54:37
...

题目描述:

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;
    }
};