121. Best Time to Buy and Sell Stock(最佳时间买卖)

1,329次阅读
没有评论

假设您有一个数组,其中的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      
admin
版权声明:本站原创文章,由admin2019-04-05发表,共计896字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)