【leetcode】121.买卖股票的最佳时机
leetcode刷题笔记-121.买卖股票的最佳时机。这道题有很多解法,特此记录一下不同的解法思路。
题目
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
1 | 示例 1: |
思路
暴力
暴力思路就是两层for循环,计算最大的差值,就是得到的最大利润
1 | class Solution { |
时间复杂度是O(N^2)
,会超时
贪心
本题思路
贪心算法,思路是枚举当前数之前的最小值,计算当前数得到的利润的最大值。
- 用一个元素来记录最小值,每一次遍历都更新这个最小值(最小的买入价格)
- 用一个元素来记录得到的最大利润,每一次遍历都更新最大利润(当前价格减去最小买入价格)
首先更新的是最大利润,再更新最小买入价格,这样能保证最小买入价格的值一定是当前元素之前的某一个值,计算出来的最大利润才有效。
1 | class Solution { |
122题 买卖股票的最佳时机2
这里顺带记录一下122题的贪心思路。122题在本题的基础上新增了一个可以多次卖出+买入的操作。而121题只能买入一次+未来卖出一次。
因为每一天都可以买入+卖出,所以我们可以把利润拆分成每一天。只要某一天买入+明天卖出的利润是正数,那么就把他加入到最终结果中。这样就相当于排除亏钱的情况,只要能赚钱就买,即可计算出最大利润。
1 | // 122. 买卖股票的最佳时机 II |
动态规划
本题思路
动态规划就要记住解题的几个步骤。
- 确定动归数组每个下标的含义
- 确定迭代方程
- 确定初始值
- 确定遍历顺序
- 举例推导
对于这道题而言,每天都有两种状态:今天持有股票和今天卖出股票。
我们可以设定dp[i][0]
是第i天持有股票时的得到的最多钱,dp[i][1]
是第i天不持有股票时得到的最多钱。很容易发现每天不持有股票得到的钱是更多的,所以最终的答案就是dp[prices.size()-1][1]
,即这个二维数组的右下角。
这里就需要两个递推公式了,先看第i天持有股票的钱
- 上一天就持有股票,即保持
dp[i-1][0]
不变; - 今天才持有股票(买入),即
-price[i]
,本题股票只能买入一次,所以选择今天买入,那么剩下的钱就是0减去股票的价格;
可得 dp[i][0] = max(dp[i-1][0],-price[i])
,上两种情况的最大值。
第i天不持有股票的钱也分为两种情况
- 上一天就没有持有股票,即保持
dp[i-1][1]
不变; - 今天才卖出股票,即保持
price[i]+dp[i-1][0]
(因为今天卖出,所以上一天肯定是持有股票的)
可得递推公式 dp[i][1] = max(dp[i-1][1],price[i]+dp[i-1][0])
;
初始化dp数组时,第0天肯定只能持有股票,不能卖出,所以初始化如下
1 | dp[0][0] = 0-price[0]; |
这里还有另外一个优化方向,从递推公式中可以看出,每一天的值只和上一天有关系,那么并不需要一个完整的二维数组,只需要一个2*2
的数组就可以了,我们把今天的值写入上一天就OK了,这样可以把空间复杂度降为O(1)
。
1 | class Solution { |
不过个人感觉这道题用动态规划来写实在是想不出来思路,而且还感觉很麻烦,还不如用贪心来处理一下。
122题 买卖股票的最佳时机2
同样记录一下122题的代码。122题和本题在动态规划上唯一的区别就是当天买入股票的时候,需要计算上一天卖出股票后能剩下的最多钱(因为同一天只能持有一张股票)
1 | // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii |
The end
股票是一系列的题目,这道题只是个简单开胃菜而已!