LC122. 买卖股票的最佳时机 II
题目描述
这是 LeetCode 上的(122. 买卖股票的最佳时机 II) ,难度为 中等。
给你一个整数数组 prices
,其中 prices[i]
表示某支股票第 i
天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
题解
动态规划
dp[i][j]
dp[i][j]
表示第i
天交易完后的最大利润j
表示是否持有股票
动态规划初始状态
dp[0][0] = -prices[0]
如果当前持有股票
- 可能前一天持有股票,今天什么都不做
dp[i][1] = dp[i-1][1]
- 可能前一天未持有股票,今天买入股票
- `dp[i][1] = dp[i-1][0] - prices[i]
- 可能前一天持有股票,今天什么都不做
如果当前未持有股票
- 可能前一天未持有股票,今天什么都不做
dp[i][0] = dp[i-1][0]
- 可能前一天持有股票,今天卖出股票
dp[i][0] = dp[i-1][1] + prices[i]
- 可能前一天未持有股票,今天什么都不做
则状态转移方程为
- 最终返回最大利润`dp[len-1][0]
代码
1 |
|
复杂度
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
动态规划(空间压缩)
- 第
i
天的状态,只与第i−1
天的状态有关 - 因此我们可以只用两个变量来维护第
i−1
天的状态 - 从而将空间复杂度优化到
O(1)
代码
1 |
|
复杂度
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
最后
- 参考了leetcode题解
LC122. 买卖股票的最佳时机 II
https://blog.daynoti.com/posts/14978/