LeetCode HOT 100(买卖股票的最佳时机)
前情回顾：
LeetCode HOT 100(爬楼梯)
【LeetCode】热题100 找出一个数组中只出现一次的数
目录
问题描述:
暴力求解(超时):
代码示例:
一次遍历求解(贪心法求解):
解题思路:
关键点:
代码示例:
动态规划求解:
五部曲解题思路:
代码示例:
问题描述:
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
暴力求解(超时):
时间复杂度O(n^2)，空间复杂度O(n)
我们需要找出给定数组中两个数字之间的最大差值（即，最大利润)。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格)。形式上，对于每组 i 和 j（其中 j >i）我们需要max(prices[j] - prices[i])
代码示例:
int maxProfit(int* prices, int pricesSize){ //暴力破解 超时 int max=0,sum=0; for(int i=0;i<pricesSize-1;i++) { for(int j=i+1;j<pricesSize;j++) { sum=prices[j]-prices[i]; max=fmax(max,sum); } } return max;}一次遍历求解(贪心法求解):
遍历一次数组:时间复杂度O(n)
有限个变量:空间复杂度O(1)
解题思路:
1、先判断今天是不是从开始到现在的历史最低点
2、如果不是最低点，那么如果今天卖股票的话，获利是不是最多的？
最后找出获利最多的结果就行了
关键点:
1：因为严格按照时间的先后顺序执行，一定要先买，在卖
2：遍历数组维护两个变量maxProfit最大的利润和minPrice最小价格。
3：如果当前价格小于最小的值minPrice时，更新minPrice的值。
4：当前前价格与最小值minPrice得差值大于maxProfi时，更细maxProfi的值
5：返回maxProfit的值
代码示例:
int maxProfit(int* prices, int pricesSize){ int maxprofit=0;//最大利润 int min=prices[0];//假设谷底为第一个数 for(int i=1;imin) { //如果后面的的前面的大，求差比较利润 maxprofit=fmax(maxprofit,prices[i]-min); } else if(prices[i]<min)//如果后面的比前面的小，后面替换前面当做谷底 min=prices[i]; //代替语句 //maxprofit=fmax(maxprofit,prices[i]-min); //min=fmin(min,prices[i]); } return maxprofit;}动态规划求解:
五部曲解题思路:
1.确定dp数组以及下标的含义
dp[i][1] 表示第i天持有股票所得最多现金
说明：其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。
dp[i][0] 表示第i天不持有股票所得最多现金
说明：“持有”不代表就是当天“买入”！也有可能是昨天或更早就买入了，今天保持持有的状态。
2.确定递推公式
如果第 i 天持有股票即dp[i][1]， 可以由两个状态推出来
第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][1]
第 i 天买入股票（第 i 天买入了也代表第 i 天持有股票），所得现金就是买入今天的股票后所得现金即： -prices[i]
那么dp[i][1]应该选所得现金最大的，所以dp[i][1] = max(dp[i - 1][1], -prices[i]);
如果第 i 天不持有股票即dp[i][0]， 也可以由两个状态推出来
第 i-1 天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][0]
第 i 天卖出股票（第 i 天卖出了也代表第i天不持有股票），所得现金就是按照今天股票佳价格卖出后所得现金即： dp[i - 1][1] + prices[i]
同样dp[i][0]取最大的，dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
3.dp数组初始化
那么dp[0][1]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][1] = -prices[0];
dp[0][0]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][0] = 0;
4.确定遍历顺序
从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。
5.返回值
因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多 dp[n-1][0];
如果不确定是哪个状态就取两个状态的最大值 max(dp[n-1][1], dp[n-1][0])
代码示例:
int maxProfit(int* prices, int pricesSize){ //动态规划 dp[i][j] 表示第i天是否持有股票 j=1持有 j=0不持有 int dp[pricesSize][2]; dp[0][0]=0; dp[0][1]=-prices[0]; //定义数组，初始化边界 for(int i=1;i<pricesSize;i++) { //第i天不持有股票;两种情况 昨天没有买，今天继续不买；昨天买了，今天卖了 dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]+prices[i]); //第i天持有股票;两种情况 昨天买了，今天没卖;昨天没有买，今天买了 dp[i][1]=fmax(dp[i-1][1],-prices[i]); } return dp[pricesSize-1][0];}感谢观看!后续持续更新LeetCode HOT 100题解
有兴趣可关注LeetCode 热题100专栏
