跳到主要内容

LeetCode 122. 买卖股票的最佳时机 II

本节目标

将无限次交易的收益拆成所有正的相邻价格差。

这是单序列扫描与边界的收益分解模型。它和单次交易都扫描价格，但证明不同：这里允许多次交易，因此应拿走每一段正向变化。

题意与约束​

每天可买入、卖出或不操作，同时最多持有一股，可完成任意多次交易。求最大总收益。

直接思路与瓶颈​

可以枚举每次买卖区间，或用状态 DP 记录持有与不持有收益。它们能得到答案，却忽略了价格路径的可加结构。

贪心模型与算法推导​

若 prices[i]>prices[i-1]，就累加这段正差值。连续上涨 a<b<c 的收益 (b-a)+(c-b)=c-a，等价于从谷底持有到峰顶；下跌差值不参与交易。这样所有上升段被无冲突地拆开。

正确性依据​

任一合法交易的收益是买卖区间内相邻价格差的和。负差值会降低收益，最优方案不会主动保留；正差值全部相加可通过连续持有或逐日买卖实现，且不会重叠。因此正差值之和既是可达到的收益，也是任何方案不能超过的上界。

样例执行过程​

[7,1,5,3,6,4] 的相邻差为 -6,+4,-2,+3,-2，只累加 4+3=7。单日 [5] 没有相邻差，答案为 0。

代码实现​

C++17
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int> prices) {
        int profit = 0;
        for (int day = 1; day < static_cast<int>(prices.size()); ++day) {
            profit += max(0, prices[day] - prices[day - 1]);
        }
        return profit;
    }
};

复杂度分析​

扫描一次即可，时间 O(n)，额外空间 O(1)。

边界与易错点​

  • 不要将单次交易的最大差值逻辑套用到本题。
  • 下跌前卖出、上涨前买入的多次交易，恰好由正差值累加表达。
  • 少于两天时循环为空，收益为零。

模式迁移​

只要目标可拆为相邻增量，且每个正增量可同时实现，就可尝试“保留所有正贡献”；若操作次数受限，需要恢复状态 DP。