贪心算法专题(四)：只赚不赔的股市神话——「买卖股票的最佳时机 II」
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第四篇！ 力扣上关于“买卖股票”的题目有一整个系列（共 6 道）。其中，第 II 题是最适合用贪心算法解决的。
规则是：你可以尽可能地完成更多的交易（多次买卖一支股票），但你手里最多只能持有一支股票（再次购买前必须卖出之前的）。
力扣 122. 买卖股票的最佳时机 II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
题目分析：
输入：价格数组
prices。目标：通过多次买卖，获得最大利润。
例子：
[7, 1, 5, 3, 6, 4]在第 2 天（价格1）买入，第 3 天（价格5）卖出，赚
4。在第 4 天（价格3）买入，第 5 天（价格6）卖出，赚
3。总利润：
4 + 3 = 7。
核心思维：利润分解
大家可能会想：我是不是要找到一个局部的最低点买入，然后再找一个局部的最高点卖出？ 比如1 -> 5，我是不是应该持有 4 天？
贪心思维的魔法：我们可以把“长线的利润”分解为“每天的利润”。 假如第 0 天买，第 3 天卖，价格是prices[0]和prices[3]。 利润 =prices[3] - prices[0]。 数学上，它等价于：prices[3] - prices[0] = (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
这意味着：“第 0 天买、第 3 天卖”的利润，等同于“第 0 天买第 1 天卖” + “第 1 天买第 2 天卖” + “第 2 天买第 3 天卖”的总和。
贪心策略：我们只需要遍历数组，计算每一天相对于前一天的差值：
如果差值是正数（今天涨了）：收下这个利润！（就当昨天买今天卖了）。
如果差值是负数（今天跌了）：不要！（我就当没操作）。
我们不需要考虑什么时候卖出，我们只需要把所有的正利润片段收集起来，就是全局最大利润！
算法流程
初始化：
result = 0。遍历数组：从第 1 天开始（下标 1）一直到最后。
计算差值：
diff = prices[i] - prices[i-1]。贪心收集：
if (diff > 0)：result += diff。
返回
result。
代码实现 (C++)
C++
#include <vector> using namespace std; class Solution { public: int maxProfit(vector<int>& prices) { int result = 0; // 从第二天开始遍历 for (int i = 1; i < prices.size(); i++) { // 今天的利润 = 今天的价格 - 昨天的价格 int dailyProfit = prices[i] - prices[i-1]; // 贪心策略：只收集正利润 // 只要涨了，我就赚这笔钱；如果跌了，我就不参与 if (dailyProfit > 0) { result += dailyProfit; } } return result; } };深度辨析：为什么能这么做？
有人会问：“如果我昨天买了，今天涨了，我卖了。但明天又涨了，我手里没股票了怎么办？”
别忘了题目规则：当天卖出后，可以当天立刻买入！
比如
1 -> 5 -> 10。贪心做法：
第一段
1 -> 5，赚 4。卖出。第二段
5 -> 10，赚 5。买入再卖出。总赚：
4 + 5 = 9。
长线做法：
1买，10卖。总赚：10 - 1 = 9。
结果是一样的！ 所以，这种“收集所有正向坡度”的策略，在没有交易手续费、没有交易次数限制的情况下，是绝对的最优解。
深度复杂度分析
时间复杂度：O(N)
只需要遍历一次数组。
空间复杂度：O(1)
只要一个变量。
总结：化繁为简的智慧
这道题展示了贪心算法通过**“数学等价转换”简化问题的能力。 我们将一个需要寻找波峰波谷的复杂决策问题，简化成了一个简单的加法问题**。
只要
p[i] > p[i-1]，就加！就这么简单。
下一题预告： 如果我们不是在炒股，而是在玩**“跳跃游戏”。 给你一个数组，每个格子里的数字代表你能向右跳的最大步数**。请问你能否跳到终点？ 这道题的贪心策略不再是累加收益，而是维护一个**“最大覆盖范围”**。只要终点在我的覆盖范围内，我就赢了！
下期见！