跳转至

121 买卖股票的最佳时机

想要得到最大利润很简单:

只需要使用最高的价钱 - 最小的成本

我们最直接的想法就是:

遍历一遍数组,得到最高价钱和最小成本,两者相减即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int minCost = INT_MAX, maxCost = 0;
        for(int i = 0; i < prices.size(); i++){
            minCost = min(minCost, prices[i]);
            maxCost = max(maxCost, prices[i]);
        }
        profit = maxCost - minCost;
        return profit <= 0 ? 0 : profit;
    }
};

但是本题有个隐藏条件:股票出售需要在买入之后,以上做法没有满足这个条件。

那么我们如何做到呢?其实也不难,我们不更新最高价钱,而是直接更新最大利润

在遍历过程中,最小成本cost取得的索引一定比prices[i]当前的索引小,因此满足题意

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cost = INT_MAX, profit = 0;
        for(int i = 0;i < prices.size(); i++){
            cost = min(cost, prices[i]);
            profit = max(profit, prices[i] - cost);
        }
        return profit;
    }
};