【算法基础】LeetCode股票交易类算法题目总结（一次交易，两次交易，无数次交易）
共 8067字，需浏览 17分钟
·
2021-03-08 00:35
大家好，前一段时间的基金市场波动很大啊，也就又诞生了很多“韭菜”，在这里千寻也提醒大家“股市有风险，入市需谨慎”，玩基金一定用不着急用的钱哦~
刷算法题目，应该是很多同学的“噩梦”，尤其是非科班的初学者，所以我准备开设一个新的话题模块——LeetCode算法刷题模块。在每一次我把刷算法题中经常遇到的一些算法题解进行整理总结。
要知道，手撕代码，也就是刷算法题的重要性在大厂面试中无可厚非，几乎所有大厂就有手撕代码环节，所以好好练习代码，刷题吧！
我更新的总结一些刷题的总结，不是简单的搬运，而是进行技巧的总结，因为在实际的面试中很有可能发生变动，所以理解算法逻辑原理才是根本，那咱们废话不多说，直接上代码题解解说。
我们第一篇就先聊聊算法题中的——股票交易类算法问题
股票交易题目内容如下：
1.买卖股票的最佳时机（一次交易）：
(1) 暴力遍历法：
（面试使用此法，容易回去等结果）
对于数组的最优条件的比较问题，最容易想到的就是暴力法，所谓暴力法就是对所有的股票买入与卖出交易情况进行枚举，依次进行逐一的交易利润的计算与统计，比较出来最大的交易利润。
时间复杂度分析：o(n²)
(要对股票价格数组进行两次遍历)
空间复杂度分析：o(1)
(只使用了常数大小的额外空间）
编写Java代码如下：
public class Solution {
public int maxProfit(int prices[]) {
int max = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit) {
max = profit;
}
}
}
return max;
}
}(2)动态规划解法：
对于使用动态规划来解决状态转换最优的题目来说，最为重要的就是建立目标状态的状态转移方程，在题目的条件下，我们可以看到在计算股票交易利润的当天是否持有股票是一个关键的状态，以此建立状态转移的二维数组dp[i][j]。
dp数组所存储的元素dp[i][j]的状态含义：
第i天时，手上的股票状态为j时的手上所持有的现金数量
（1）j=0 ，表示当前不持有股票的状态
（2）j=1 ，表示当天持有股票的状态
编写Java代码如下：
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// 特殊判断
if (len < 2) {
return 0;
}
int[][] dp = new int[len][2];//使用两列的数组表示0,1两种状态
// dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
// dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数
// 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 从第 2 天开始遍历
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[len - 1][0];
}
}时间复杂度分析：o(n)
（遍历动态数组得到最优解）
空间复杂度分析：o(n)
（新建了一个状态数组大小为N）
2.买卖股票的最佳时机（两次交易）
与上一道算法题不同之处在与本次股票交易需要进行两次交易所得利润的最大之和，也就是就是在整个的过程中，会有两次“买入卖出”的操作，你需要对两次股票交易所得利润求得计算利润的总和。
算法流程：
（1）建立一个dp动态规划数组dp[len][i],状态数组中包括五个状态，
dp动态规划数组中的所存储的元素dp[j][i]的含义：
dp[j][i]表示在第j天的时候状态为i时，股票的最大收益，
状态转换数组初始化：
(1)初始化第一次买入的时候股票的收益为dp[0][1]=-prices[0]
(2)初始化第三次买入的时候股票的收益为dp[0][3]=-prices[3]
可能最大的疑惑在于为何此时初始化的元素为负数，因为买入股票，相当于购买了股票此时的利润为-prices[0], 处于赔钱状态，求最大利润的时候，只需要计算比较dp数组中四个状态下的最大值。
编写Java代码如下：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
if (prices.length == 0) return 0;
int [][]dp = new int[prices.length][5];
//初始化
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = dp[i - 1][0];
//其中dp[i][1]有两个操作1）第i天没有操作2）第i天买入股票，所以此时最大收益，应该为这两个操作比大小
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//其中dp[i][2]有两个操作1）第i天没有操作2）第i天卖出股票，所以此时最大收益，应该为这两个操作比大小
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//其中dp[i][3]有两个操作1）第i天没有操作2）第i天买入股票，所以此时最大收益，应该为这两个操作比大小
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//其中dp[i][4]有两个操作1）第i天没有操作2）第i天卖出股票，所以此时最大收益，应该为这两个操作比大小
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.length - 1][4];
}
}3.买卖股票的最佳时机（无数次交易）
本题相比于前面的两道题目来说，又一次进行了扩展，从一次交易限制条件下的转化为了可以进行无数次的买入与卖出交易，相当于对题目的限定条件进行了释放，只要存在卖出股票价格高于买入的股票值，都可以加入最终的利润。
算法流程：
(1)初始化股票交易的最大利润的总值sum=0;
(2)比较今天的股票价格与前一天的股票价格，如果今天的股票价格比前一天的股票价格高，则说明可以带来正向收益，可以计算加入正向的最终收益。
编写Java代码如下:
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
if(prices.length==0||prices==null){
return 0;
}
int sum=0;
for(int i=1;i<prices.length;i++){
if(prices[i]-prices[i-1]>0){
sum+=prices[i]-prices[i-1];
}
}
return sum;
}
}股票的收益问题在算法面试的考察中，算是比较高频的考点了，接下来我会不定期的更新算法题解的总结，分享刷题的心得，加油！
我是千与千寻，我们下期再见~
往期精彩回顾
本站qq群704220115，加入微信群请扫码：