LeetCode买卖股票之一:基本套路(122)
欢迎访问我的GitHub
这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos
关于《LeetCode买卖股票》系列
- 在LeetCode上,有数道和买卖股票有关的题目,覆盖了简单、中等、困难,要求都是选择低价时间买入、高价时间卖出,以求达到利润最大化
- 这类题型的特点就是:典型的动态规划题型,掌握套路后,越做越开心,就算难度是困难的题目,也能从容面对
- 于是,欣宸将此类题目聚集在一起,集中火力分析和解题,构成了《LeetCode买卖股票》系列,在该系列中,欣宸与您一同打好基础,再将该类型题目逐个攻克,在LeetCode世界中做一回股神
本篇概览
- 对之前的解题经历做了认真回顾后,我这边决定用第122题《买卖股票的最佳时机 II》作为系列的开篇,原因是此题在所有买卖股票的文章中最为典型:题目具备代表性,同时其他题目中奇怪的约束条件如冻结期、交易次数等,在122题中都不存在,写出的状态转移方程可以作为其他题目的参考
- 接下来开始做题吧,先看题目
题目信息
- 题号:122
- 难度:中等
- 描述
- 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
- 在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
- 返回 你能获得的 最大 利润 。
- 示例 1:
输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
- 示例 2:
输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
- 示例 3:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。
- 提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
核心问题分析
- 解题的关键,是搞清楚两个最核心的问题:
- 我们要的是什么?
- 变化有哪些?
第一个问题:我们要的是什么?
- 认真审题后,我们要的东西可以这样描述:第i天股市结束后手里的最大利润
第二个问题:有哪些变化?
- 很容易发现,一共有两种变化:和行为无关、和行为有关
- 和行为无关的变化:是时间和股价,只要知道是第几天,也就知道了股价,所以只要聚焦时间变化即可
- 和行为有关的变化:股票持有情况,即持有和不持有
确定dp定义
- 弄清楚上述两个问题后,dp定义也就呼之欲出了:
- dp数组的值就是我们想要的东西
- dp数组的维度就是变化,一共有两个变化,所以一共有两个维度
- 于是,我们对dp数组的定义如下图
- 上图中,i的取值好理解,表示第几天,至于j,我们规定它只有两个值:0和1,0代表不持有股票,1代表持有股票
- 下图是个例子,很容易理解:第3天股市结束后,未持有股票时,手里的最大利润是123元
状态转移方程分析
- 要想写出状态转移方程,首先要弄明白状态是怎么变化的,时间状态自不必分析,它是客观在变化的,我们要弄明白的是另一个状态:股票持有状态,严格来说要弄清楚两点:
- 第i天股市结束后,如果手里持有股票,这个股票是从哪来的?
- 第i天股市结束后,如果手里没有股票,为什么手里会没有股票?
- 只要弄清楚上述两个问题,状态转移方程也就出来了,接下来逐个分析
手里持有股票的原因
- 第i天股市结束后,如果手里持有股票,有两种可能:
- 第i天之前持有股票,到了第i天啥也不做,此时:dp[i][1]=dp[i-1][1]
- 第i天之前不持有股票,在第i天购买了,此时:dp[i][1]=dp[i-1][0]-price[i],因为购买要花钱,所以用手里的钱减去当天股价
- 我们要的是最大利润,所以应该取上述两种情况的最大值
- 现在可以写出dp[i][1]的表达式了:dp[i][i]=Math.max(dp[i-1][1], dp[i-1][0]-price[i])
- 一图胜千言,看过下图您就一定明白了
手里未持有股票的原因
- 接下来继续分析,第i天股市结束后如果手里没有股票,有两种可能导致:
- 第i天之前未持有股票,到了第i天啥也不做,此时:dp[i][0]=dp[i-1][0]
- 第i天之前持有股票,在第i天卖出,此时:dp[i][0]=dp[i-1][1] + price[i],因为卖出股票会换来钱,所以这里用手里的钱加上当天股价
- 我们要的是最大利润,所以应该取上述两种情况的最大值
- 现在可以写出dp[i][0]的表达式了:dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+price[i])
- 一图胜千言,看过下图您就一定明白了
- 状态转移方程已经出来了,接下来按部就班写好代码提交即可
编码
- 有了上面的分析,相信此刻您也能流畅的完成编码了,参考代码如下
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
// 第0天股市结束后,如果手里没有股票,那就是没有购买过,此时最大利润只能等于0
// 初始化为0的代码可以省去
// dp[0][0] = 0;
// 第0天股市结束后,如果手里有股票,那就是当前购买的,此时最大利润就是负数
dp[0][1] = -prices[0];
for (int i=1;i<prices.length;i++) {
// 第i天股市结束时,手里没有股票的原因有两个:
// 1. 之前就没有股票,第i天啥样没做
// 2. 之前有股票,第i天卖出
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
// 第i天股市结束时,手里有股票的原因有两个:
// 1. 之前就有股票,第i天啥样没做
// 2. 之前没有股票,第i天买入
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
// 第i天结束后,手里不持有股票的最大利润就是返回值
return dp[prices.length-1][0];
}
}
- 提交代码,如下所示,虽然AC了,但是速度很一般,超过26.27%的提交,显然还有优化空间
优化
- 回顾上述代码中,dp[i][0]和dp[i][1]都是通过dp[i-i][0]和dp[i-1][1]计算出来的,如此看来,这个dp二维数组似乎有些浪费,用下面这四个变量足矣
- prevWithStock:前一天股市结束后,手里有股票时的最大利润
- prevWithoutStock:前一天股市结束后,手里没有股票时的最大利润
- currentWithStock:当天股市结束后,手里有股票时的最大利润
- currentWithoutStock:当天股市结束后,手里没有股票时的最大利润
- 优化后的代码如下
class Solution {
public int maxProfit(int[] prices) {
// 第0天股市结束后,如果手里有股票,那就是当前购买的,此时最大利润就是负数
int prevWithStock = -prices[0];
// 第0天股市结束后,如果手里没有股票,那就是没有购买过,此时最大利润只能等于0
int prevWithoutStock = 0;
// 当天股市结束后,如果手里有股票时的最大利润
int currentWithStock;
// 当天股市结束后,如果手里没有股票时的最大利润
int currentWithoutStock = 0;
for (int i=1;i<prices.length;i++) {
currentWithoutStock = Math.max(prevWithoutStock, prevWithStock + prices[i]);
currentWithStock = Math.max(prevWithStock, prevWithoutStock - prices[i]);
prevWithStock = currentWithStock;
prevWithoutStock = currentWithoutStock;
}
// 第i天结束后,手里不持有股票的最大利润就是返回值
return currentWithoutStock;
}
}
- 再次提交,稍微提升了一点
- 至此,买卖股票的基本套路,以及状态转移方程设计思路和实现,咱们已经学习到了,接下来的文章中,都会基于这个思路去设置状态转移方程
- 当然了,此刻您应该还有个疑问:为何速度的排名如此之低?接下来咱们来看看落后的原因
为啥排名不高?
- 这道题本身也有一些特殊:除了动态规划,贪心算法也能解
- 以prices={1, 2, 3}为例,聪明的您应该看出来了,如果1买入,3卖出,得到的利润等于2,属于最大利润
- 题目有个约束:一天不能既买入又卖出,如果跳出这个约束,那就可以做到1买入2卖出,然后2买入3卖出,利润还是2!
- 至于能不能将3-1转化成(3-2)+(2-1)呢?当然可以,减去2再加上2,对原题的结果毫无影响,却可以改变代码流程,如下所示,每当买入卖出能赚钱时,就将插件累加起来,这样的计算中,相比前面的代码,每次循环中的计算量明显减少了
class Solution {
public int maxProfit(int[] prices) {
if (prices.length<2) {
return 0;
}
int total = 0;
for (int i=1;i<prices.length;i++) {
if (prices[i]>prices[i-1]) {
total += prices[i] - prices[i-1];
}
}
return total;
}
}
- 再次提交,这回超越了百分百
- 至此又得出一个结论:本题用动态规划做并没有错,也不是动态规划代码没写好,而是有更高效的贪心算法恰巧也能解决此问题
- 经过本篇实战,相信您对动态规划以及股票买卖问题都有了更深的理解,接下来,继续挑战其他股票买卖问题,在LeetCode世界中向着股神前进
欢迎关注博客园:程序员欣宸
热门相关:我有一座冒险屋 隐婚试爱:娇妻,好甜! 我是仙凡 重生之将门毒后 重生之女将星