牛客题霸--买卖股票的最好时机

买卖股票的最好时机

题目链接

Solution

因为只有一次买入卖出的机会,所以可以枚举在哪天卖出。
对于卖出的那一天,买入的那一天一定在这一天之前,并且是价格最低的。
所以从前往后扫,记录并更新最小值即可。

Code


class Solution {
public:

    int maxProfit(vector<int>& prices) {
        // write code here?
        int ans = 0, mn = prices[0];
        for (int i = 1; i < (int)prices.size(); ++i) {
            ans = max(ans, prices[i] - mn);
            mn = min(mn, prices[i]);
        }
        return ans;
    }
};
上一篇:【模板】单源最短路径(标准版)


下一篇:[ARC101C] Ribbons On the Tree