美文网首页
Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

作者: 你过来啊2018 | 来源:发表于2018-02-25 20:50 被阅读0次

    问题链接

    https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/572/

    解题思路

    思路一:两次遍历寻找前后两个数的最大差值,发现超时,时间复杂度O(n^2)
    思路二:遍历一次,迭代更新最小值,并计算最小值与最新遍历点的差值,最大的即为最大交易

    代码(思路二)

    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            maxprofit = 0
            if len(prices) == 0:
                return maxprofit
            low = prices[0]
            for i in range(1, len(prices)):
                if prices[i] < low:
                    low = prices[i]
                else:
                    profit = prices[i] - low
                    if maxprofit < profit:
                        maxprofit = profit
            return maxprofit
    

    相关文章

      网友评论

          本文标题:Best Time to Buy and Sell Stock

          本文链接:https://www.haomeiwen.com/subject/hgfdxftx.html