假设您有一个数组,其中的ith元素是第i天给定股票的价格。
如果你只被允许完成至多一笔交易(即买一份,卖一份股票),设计一个算法来找到最大利润。
请注意,在购买股票之前,您不能出售股票。
Example 1:
<strong>Input:</strong> [7,1,5,3,6,4] <strong>Output:</strong> 5 <strong>Explanation:</strong> Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
<strong>Input:</strong> [7,6,4,3,1] <strong>Output:</strong> 0 <strong>Explanation:</strong> In this case, no transaction is done, i.e. max profit = 0.
解法
具体的逻辑说明在代码备注里面
class Solution: def maxProfit(self, prices: List[int]) -> int: #如果当前列表长度小于2那么直接返回结果,因为你没有任何交易机会 if len(prices)<2: return 0 #我们需要三个变量记录,min_index最小买入时间索引, #同理最大,profit记录最大利润 min_index=0 max_index=0 profit=0 #循环遍历数据 for ind in range(1,len(prices)): #判断当前的价格大于历史最高价 if prices[ind]>prices[max_index]: max_index=ind #计算当前的利润 curr_profit=prices[max_index]-prices[min_index] #如果利润大于历史利润则使用当前利润 if curr_profit>profit: profit=curr_profit #获取最小买入价格,如果最小买入时间索引大于 #最大卖出索引,则需要对最大卖出索引处理 elif prices[ind]<prices[min_index]: min_index=ind if min_index>max_index: max_index=min_index return profit