LeetCode第121题:买卖股票的最佳时机(python)

2021/8/1 20:05:56

本文主要是介绍LeetCode第121题:买卖股票的最佳时机(python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:
在这里插入图片描述
思路1:
暴力求解,用两层循环,用来寻找最大差值,非常简单(但在LeetCode上大概率出现超时的情况)
代码如下:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        ans = 0
        if n == 0:
            return 0
        for i in range(n):
            for j in range(i+1, n):
                maxprice = prices[j] - prices[i]
                ans = max(ans, maxprice)
        return ans

思路2:
为了降低时间复杂度,这里我用到了动态规划的方法,动态规划最关键的点在于状态转移方程,设dp[i]为当前两个数的最大差值,minprice为最小值,则有dp[i] = max(dp[i - 1], prices[i] - minprice),因此就可以写代码了。

代码如下:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        dp = [0 for _ in range(len(prices))]
        # 设minprice的初始值为prices的第0个值
        minprice = prices[0]
        for i in range(1, len(prices)):
        	# 从数组下标为1开始,更新最小值
            minprice = min(minprice, prices[i])
            # 每次都将最大差值加入dp
            dp[i] = max(dp[i - 1], prices[i] - minprice)
		# 此时的dp是顺序排列的,最后一个值就是最大的
        return dp[-1]


这篇关于LeetCode第121题:买卖股票的最佳时机(python)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程