抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

25 | 面试题:买卖股票的最佳时机 贪心解法

122. 买卖股票的最佳时机 II

背景:只能持有一股,买卖无数次。保证收益最大化。

解法一:搜索,DFS 深度搜索。

每天可以有两个操作:

  1. 买一股
  2. 卖一股

遍历每个元素,记录买一股买一股的收益,递归的找出收益最大的操作。

时间复杂度:O(2ⁿ)

解法二:贪心算法

思想:只要后一天的价格比前一天的价格高,那么就在前一天买进,后一天卖出即可。

决定是否可行条件:是否可在同一天进行买进与卖出。同时无交易手续费,所以可以频繁交易。

实现:写一层循环,判断后一天比前一天高时,在前一天买进,后一天卖出即可。然后把所有的收益加上即可。

时间复杂度:O(N)

解法三:动态规划 DP

把每一天之前的这个状态都记下来,也就是针对每一种天数列一个状态,这个状态是:以后1股的时候利润是多少,0股的时候利润是多少,把最大的利润保存好。然后每天就和前面的这一天进行对比,是卖出还是买进。

时间复杂度:O(N)

动态规划可解决的问题,比贪心多。但老师这节课并不是主要讲这个。

详细题解:暴力搜索、贪心算法、动态规划


0条评论

发表评论