leetcode 121：买卖股票的最佳时机(python)

心已赠人 2024-04-19 13:21 45阅读 0赞

# 题目 #

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: \[7,1,5,3,6,4\]  
输出: 5  
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。  
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。  
示例 2:

输入: \[7,6,4,3,1\]  
输出: 0  
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解法一 #

*  思路  
    记录最低值，不断更新最高值寻找其中差值最大者
 *  代码

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            lens=len(prices)
            if lens<2:
                return 0
            maxpro=0
            lpri=prices[0]
            for i in range(1,lens):
                if prices[i]<lpri:
                    lpri=prices[i]
                elif prices[i]>lpri:
                    maxpro=max(maxpro,prices[i]-lpri)
            return maxpro

*  结果  
    ![在这里插入图片描述][20190922133927758.png]

# 解法二 #

*  思路  
    参考：  
    [121. 买卖股票的最佳时机 - dp 7 行简约风格][121. _ - dp 7]  
    求相邻两天的差值，然后问题就变为了求最大连续子数组和，
 *  代码

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            temp=maxpro=0
            for i in range(1,len(prices)):
                temp= max(0,temp+prices[i]-prices[i-1])
                maxpro= max(maxpro,temp)
            return maxpro

*  结果  
    ![在这里插入图片描述][20190922135352546.png]

[20190922133927758.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c8a9b436c12d44d48b11488174e68a9a.png
[121. _ - dp 7]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
[20190922135352546.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/898d2b3f108c492588a104c2ed86ded5.png