LeetCode刷题复盘笔记—一文搞懂贪心算法之122. 买卖股票的最佳机遇 II题目
本日主要总结一下可以使用贪心算法解决的一道标题，122. 买卖股票的最佳机遇 II标题：122. 买卖股票的最佳机遇 II
Leetcode标题地点
标题形貌：
给你一个整数数组 prices ，其中 prices 表现某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices =
输出：7
表明：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices =
输出：4
表明：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices =
输出：0
表明：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 104
0 <= prices <= 104
本题重难点
这道题之前用动态规划算法进行过详细讲解一文搞懂动态规划之122. 买卖股票的最佳机遇 II题目，同时这道题还可以使用贪心算法解决！
本题首先要清楚两点：
只有一只股票！
当前只有买股票或者卖股票的利用
想获得利润至少要两天为一个交易单元。
贪心算法思绪：这道标题可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…循环反复。
如果想到着实最终利润是可以分解的，那么本题就很容易了！
怎样分解呢？
假如第0天买入，第3天卖出，那么利润为：prices - prices。
相当于(prices - prices) + (prices - prices) + (prices - prices)。
此时就是把利润分解为每天为单元的维度，而不是从0天到第3天整体去思量！
那么根据prices可以得到每天的利润序列：(prices - prices)…(prices - prices)。
如图：
https://i-blog.csdnimg.cn/blog_migrate/d10263d2120d430c0537e14781093836.png
一些同学陷入：第一天怎么就没有利润呢，第一天到底算不算的困惑中。
第一天当然没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！
从图中可以发现，着实我们须要网络每天的正利润就可以，网络正利润的区间，就是股票买卖的区间，而我们只须要关注最终利润，不须要记录区间。
那么只网络正利润就是贪心所贪的地方！
局部最优：网络每天的正利润，全局最优：求得最大利润。
局部最优可以推出全局最优，找不出反例，试一试贪心！
C++代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i = 1; i < prices.size(); i++){
res += max(prices - prices, 0);
}
return res;
}
};
时间复杂度：O(n)
空间复杂度：O(1)
总结
股票题目着实是一个系列的，属于动态规划的范畴，贪心算法只能解决部门题目，动态规划算法才是解决股票题目的体系性解法，所以使用动态规划算法解决股票题目使用动态规划算法解决122. 买卖股票的最佳机遇 II题目必须要掌握！
这篇文章可以看出偶然候，贪心每每比动态规划更巧妙，更好用，所以别小看了贪心算法。
本题中理解利润拆分是关键点！ 不要整块的去看，而是把整体利润拆为每天的利润。
一旦想到这里了，很天然就会想到贪心了，即：只网络每天的正利润，最后稳稳的就是最大利润了。欢迎各人关注本人公众号：编程复盘与思考漫笔(关注后可以免费获得本人在csdn发布的资源源码)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]