LeetCode 122 买卖股票的最佳时机 多笔交易贪心算法 C++进阶题解

大家好，今日打卡分享股票系列进阶算法题「买卖股票的最佳时机 II」。本题是121题的升级版本，核心从单次交易升级为允许多次买卖，是贪心算法进阶应用的经典题型，也是大厂笔试高频考点。

题目题意

给定股票每日价格数组，交易规则：

1. 可以无限次买入卖出股票
2. 任意时刻最多只能持有1股（必须先卖出才能再次买入）
3. 同一天可以多次买卖（无实际收益，不影响结果）
目标：计算可获取的最大总利润；无获利时返回0。

核心解题思路：贪心累加所有正差值

本题最优解法的核心逻辑非常巧妙：

- 股价上涨区间的利润，等价于所有相邻上涨差值的总和
- 例如： [1,3,5] 一次性买入卖出利润 = 5-1 = (3-1)+(5-3)
- 遍历所有相邻交易日，只要后一天价格更高，就累加利润差值；下跌区间直接跳过
全程仅一次遍历，时间复杂度O(n)，空间复杂度O(1)，是本题最优解法。

样例原理讲解

输入 prices = [7,1,5,3,6,4] ：

- 相邻正差值： 5-1=4 、 6-3=3
- 总利润 = 4+3 = 7，与样例输出完全匹配
输入 prices = [1,2,3,4,5] ：
- 所有相邻差值累加： 1+1+1+1 = 4 ，等价于一次性买卖利润

C++完整AC代码实现

class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for(int i = 1; i < prices.size(); i++){
// 只累加上涨的利润，下跌利润取0
profit += max(prices[i] - prices[i-1], 0);
}
return profit;
}
};


算法考点总结

这道题是贪心思想的进阶应用：局部最优（每次上涨都获利）可以推导出全局最优（总利润最大）。
掌握这套「累加正差值」的模板，能快速区分单次/多次股票交易的解题差异，是动态规划、贪心算法入门的关键里程碑。