LeetCode 121 Best Time to Buy and Sell Stock

LeetCode 121 Best Time to Buy and Sell Stock

Say you have an array for which the i^th 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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

题目大意：

如果你只能进行一次交易（比如购买或者销售一个股票），设计一个算法来获取最大利润。

解题思路：

利润=当前价格-买入价，利润作为第一个变量求其最大值。由于买入价越低，利润可能会越大，所以第二个变量就要不断更新买入价
（最小值）。本题核心思路就是维护两个变量：最低价，利润。为什么不用最高价而选择利润呢？因为最低价和最高价没有顺序，最高价
必须在最低价后面，这样的利润才可实现，但如果是最低价和利润，就能确保这个顺序了，因为利润一定是在最低价后，否则这个利
润为负，不能为最大值。另一种稍麻烦的方法是凡是min更新，最高价就reset为0，大原则就是保持顺序。

注意事项：

数组为空

Python代码：

def maxProfit(self, prices: List[int]) -> int:
	min_buy_idx, max_profit = 0, 0
	for i in range(len(prices)):
		max_profit = max(max_profit, prices[i] - prices[min_buy_idx])
		if prices[i] < prices[min_buy_idx]:
			min_buy_idx = i
	return max_profit

Java代码：

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	int min = prices[0];
	int curProfit = 0;
	for(int i=1;i<prices.length;i++){
		int todayProfit = prices[i]-min;
		if(todayProfit>curProfit)
			curProfit = todayProfit;
		if(min>prices[i])
			min = prices[i];
	}
	return curProfit;
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(1)。

KK's blog