[LeetCode 121] Best Time to Buy and Sell Stock

作者 Shilei Tian 日期 2016-04-10
[LeetCode 121] Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

其实这道题目应该算是比较简单的题目,但是如果不仔细考虑,很容易就出错。上去肯定能够想到的算法就是,买入一定要在卖出前面,那么一个很暴力的算法就会有:

class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) {
return 0;
}
int maxProfit = 0;
for (int out = 0; out < prices.size(); ++out) {
for (int in = 0; in < out; ++in) {
if (prices[out] - prices[in] > maxProfit) {
maxProfit = prices[out] - prices[in];
}
}
}
return maxProfit;
}
};

该算法时间复杂度为O(n^2),在 LeetCode 下会超时,那么我们就需要仔细考虑这个问题。下面介绍一下时间复杂度为 O(n) 的算法,代码如下:

class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) {
return 0;
}
int maxProfit(0), minIndex(0), maxIndex(0);
for (int i = 0; i < prices.size(); ++i) {
if (prices[i] > prices[maxIndex]) {
maxIndex = i;
int currentProfit = prices[maxIndex] - prices[minIndex];
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
} else if (prices[i] < prices[minIndex]) {
if (i < maxIndex) {
minIndex = i;
int currentProfit = prices[maxIndex] - prices[minIndex];
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
} else {
minIndex = maxIndex = i;
}
}
}
return maxProfit;
}
};

最初将买入和卖出时间都初始化为时间点 0,这样最大的收益也是 0

对于每一次迭代,先判断这次的值是否比最大的还要大,如果是的话,这将会是一个比较好的卖出时机,计算此时的收益,如果比最大收益还要大,那么记录它。

如果它没有最大的大,那么我们之前肯定有比这个更好的卖出时机,所以我们就不考虑卖出,考虑买进时机。如果此时价格比之前出现过最低的价格还要低,并且 i 的值比最大的 maxIndex 要小,那么这个肯定会是一个很好的买进时机。但是如果这个值比 maxIndex 大的话,那么我们在这之前都不能买入和卖出,否则必然会是赔钱的!所以我们就要从这里重新考虑买入卖出,将 minIndexmaxIndex 都设为 i 继续迭代。