【刷题日记】干就完了,122. 买卖股票的最佳时机 II
本次刷题日记的第 88 篇,力扣题为:122. 买卖股票的最佳时机 II
一、题目描述:
继续来搞钱,买卖股票的最佳时机 II
二、这道题考察了什么思想?你的思路是什么?
买卖股票,上次我们做一次初阶版本的,这次我们来做第二个版本的买卖股票的题,上次买卖股票,我们来比较初级,给出的股票的咱们只能买一次,卖一次,然后计算最大利润
这一次不一样的了,咱们可以在给出的多天股票价格里面,我们可以在任意天买卖,但是同一时间,我们的手上只能有 1 支股票
根据本题的要求,我们可以在同一天买股票和卖股票,还是同样的,要求我们计算最大的利润
分析
上次咱们的想法是,认为只要我们买,那么那就当做是未来最低点,然后计算出未来卖出的最高点,来计算出最大利润
那么这一次,我们该如何去看待这个题呢
既然咱们可以买了又卖,卖了又买,我们是不是可以延续上一次做题的想法,我认为咱们多次的买卖中,只要是有利润的,我们就买,然后就卖,每天都去看看我们是买还是卖,当然,只有获利的时候我们才会卖
当然,这里说的买可不是真的交易,只是咱们为了计算最大利润而去贪心的来模拟的,简单来说,咱们如果确定昨天买入,今天卖出,有利可图,那么就干,如果不行,就看下一天,最终将利润求和,就得到了最大利润和
例如,题目中的示例 1:
源数组 | 7 | 1 | 5 | 3 | 6 | 4 |
---|---|---|---|---|---|---|
当前利润和 | 0 | 0 | 4 | 4 | 7 | 7 |
咱们这就可以看出,在第 3 天的时候,我们就可以获利 4 元,第 5 天就可以获利 4+3 元,总共就是交易两次
同理,题目中的示例 2 ,我们还是用同样的方式,来看
源数组 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
当前利润和 | 0 | 1 | 2 | 3 | 4 |
就这么来看,可能以为咱们是交易了 4 笔,实际上按照题目中的逻辑,应该是就交易了 1 笔,第 1 天买入,第 5 天卖出,获利 4 元
所以,题目是要咱们计算最大利润,我们就可以通过这种贪心的方式来处理,如果是要计算交易最少笔数的话,我们这种方式就需要调整一下了
三、编码
根据上述逻辑和分析,我们就可以翻译成如下代码
- 咱们翻译代码的时候就贪心的每天都去看股票,看是否适合买是否适合卖,适合就干
编码如下:
func maxProfit(prices []int) int {
var res int
for i:=1; i<len(prices); i++ {
res += max(0, prices[i]-prices[i-1])
}
return res
}
func max(a,b int) int {
if a>b {
return a
}
return b
}
四、总结:
咱们本次的这种做法的时间复杂度是 O(n) ,咱们只遍历了一遍题目给出的 prices 数组
空间复杂度是 O(1) ,咱们引入的都是常数级别的空间消耗
原题地址:122. 买卖股票的最佳时机 II
今天就到这里,学习所得,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~
转载自:https://juejin.cn/post/7130263208770109454