Leetocode6‎道买卖股票问题总结(121 122 123 188 309 ‎90‎1)

来源:m-dot.com   作者:   发表时间:2020-02-21 04:27:01

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

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

buy[i]记录截止到第i天是买入的状态的最小花费(值为负数)

严格来说这个不算dp,计算第i天的情况时,只用到了buy[i-1]的数据。。所以前面保存的数据是没有意义的。

dp[i]记录第i天当天卖出的最大利润,则最大利润一定等于之前某天买今天卖。

i):首先可以昨天买今天卖。

ii):还可以之前某天买今天卖。dp[i-1]等于昨天之前买入,i-1天卖出的最大利润,那么i-1天不卖,改为第i天卖也可以得到一个利润。

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

定义了4个dp数组,分别是

buy1[i]:第i天是第一次买入的状态

sell[i]:第i天是第一次卖出的状态

buy2、sell2同理。

由于一开始还不能第二次买和第二次卖,所以赋值为负无穷。

方法2:先计算1次买卖最大的利润sell1[i]。再计算从第i天开始再买卖一次最大的利润sell2[i]。

第一次买卖是从前向后求(因为左侧是固定的),第二次买卖是从后向前求(因为右侧是固定的)

之前写过的python版本,以供参考:

后来发现其实不需要存储dp数组,只需要一个变量记录上一次的状态就行,但我懒,就不写了,反正内存大任性

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。

这道题限制买卖次数最大为k,是一个变量。

设二维dp数组。dp[i][j]表示截止到i最多完成j笔交易的最大利润。

截止第i天,最大利润首先可以是之前的最大利润,即之前就完成了j笔交易,第i天不卖。

当然第i天也可以卖,那么本拨交易的买入最晚也得是i-1天,那么i-2天之前(包含i-2天)就必须要完成j-1笔交易。

用一个max值表示截止到前一天完成j-1笔交易、并且是待卖出状态的最大利润。

递推方程为:dp[i][j]=max(dp[i-1][j],max prices[i])

另外每次循环中要更新max的值。

另外有用例k给的无限大,那么申请dp数组时会爆栈。需要判断一下k和价格数量的关系,如果k太大,转化为上面第2题的无限次的买卖股票问题。

前面的问题1和问题3只是这道题的特殊情况,代码直接复制过去就可以运行。

给定一个整数数组,其中第i个元素代表了第i天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

这道题多了一个冷冻期的限制:卖出之后要至少休息一天才能买入

那么理所当然的,多设立一个dp数组以表示冷冻期的状态:

也可以仿照第四题的解法,用一个max值保存截止前一天待卖出状态的最大利润,不过更新max的时候,要注意冷冻期的要求。所以_max=max(_max,dp[i-2]-prices[i]),即截止i-2天卖出的最大利润,休息一天,第i天买入。之前的题目是_max=max(_max,dp[i-1]-prices[i]),注意二者的区别,虽然只是1和2的数字不同,但却是整道题的关键

编写一个 StockSpanner 类,它收集某些股票的每日报价,并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。

例如,如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85],那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

其实题目就是找今天之前最近的比今天价格大的一天,如果是从昨天顺序往前查找,时间复杂度太高。下面有两种方法可以优化时间效率。

方法1:DP,有最大、最小、最多这种字眼的一般都是DP,极个别可能是DFS。

用一个一维数组dp,dp[i]表示第i天的股票价格跨度。如果i-1天的价格小于等于第i天,那么dp[i]可以直接加上dp[i-1]的值,这是因为dp[i-1]是小于等于i-1天价格的连续天数,而且i-1天价格还不大于第i天。

拿题目中的数组举栗子,当前第5天,之前0~4天的价格:100, 80, 60, 70, 60;已经算好的dp数组:1,1,1,2,1。

那么第5天价格75,i-1=4,第4天价格60,dp[4]=1,dp[i]可以加1。下面考虑4-1=3天

此时考虑第3天的价格为70,依然小于等于75,所以dp[i]再加dp[3]=2。下面考虑3-2=1天

再考虑第1天,发现其价格80>75,则退出。

概括点说,就是利用空间换取时间,保存了每一段跳跃的天数,求某一天的结果时,不再顺序查找,而是利用之前保存的数据,每次跳一大步直到目的地。平均来说,跳跃的步数应该为1。

时间O(N),空间O(N)

方法2:单调栈,这个是看题解来的,记录在一起。

其实之前也做过单调栈的题目,好像也是在leetcode上的,什么天际线的。但碍于相关题目不多,没有系统学过,做题时想不起来这个方法。

原理是这个题对于今天如果价格是100,那么今天以前的所有价格小于等于100的天的数据就不需要存储了,即数据结构中之前存储的比当前数更小的数就移除。这个性质正好符合递减栈,如果栈顶小于等于当前要push的数字,就把栈顶pop掉。直到栈顶大于当前要push的数字,再push。

还是用题目的例子:如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85],那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]

我们用两个同步栈(即同时push,同时pop)来做。当然设置一个新struct里面包含价格和价格跨度两个变量也可以用一个栈。。

价格栈prices,跨度栈(即保存结果的栈)kuadu。

最开始prices push无穷大,kuadu push1,这样依然可以保持递减栈性质,不影响结果,为了省去后面判断栈空的代码。。(你不push也可以)

1.  100<无穷大(下面用inf表示),push

两个栈:inf ,100        1,1

2.  80<100,push

两个栈:inf,100,80      1,1,1

3.  60<80 ,push

两个栈:inf,100,80,60      1,1,1,1

4.  70>60 ,当前跨度初始值tmp为1,因为自己也小于等于自己。然后tmp =跨度栈的栈顶(1),1 1=2

两个栈:inf,100,80        1,1,1

  70<80,push:价格栈push70,跨度栈push tmp

两个栈:inf,100,80,70      1,1,1,2

编辑:

未经授权许可,不得转载或镜像
© Copyright © 1997-2019 by m-dot.com all rights reserved