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]当前的索引小,因此满足题意