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

假设您有一个数组，其中的 ith 元素是第 i 天给定股票的价格。

如果你只被允许完成至多一笔交易（即买一份，卖一份股票），设计一个算法来找到最大利润。

请注意，在购买股票之前，您不能出售股票。

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: 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:

Input: [7,6,4,3,1]
Output: 0
Explanation: 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