买卖股票 II 图解题解

这道题到底在问什么

prices

[7, 1, 5, 3, 6, 4]

输出

7

先想最直接的笨办法

最直接的念头是「找一个谷底买进、找一个峰顶卖出」。但能交易很多次，到底切成几段、每段谷峰在哪，枚举起来又乱又慢，而且根本没必要知道具体的买卖点。（动画第 3 步）

最优解：一步一步想明白

1. 3最直接的念头是「找一个谷底买进、找一个峰顶卖出」。但能交易很多次，到底切成几段、每段谷峰在哪，枚举起来又乱又慢，而且根本没必要知道具体的买卖点。
2. 4换个角度：把利润拆到每一天。今天比昨天涨，就把这点差价收进口袋（相当于昨天买、今天卖）；今天比昨天跌，就空仓什么都不做（加 0）。为什么成立：一段连续上涨 1→5 的总收益 4，正好等于它每天小涨之和；所以「把所有正的日差累加」和「整段买卖」收益完全相等，而且不限次数让我们可以自由分段——逐日贪心就是全局最优。
3. 5profit = 0利润 profit 从 0 起。第 1 天（价 7）没有前一天可比，cur 先停在这里，真正的累加从第 2 天开始。
4. 6diff = 1 − 7 = −6走到第 2 天（价 1），先算今天减昨天：1 − 7 = −6，是负的。
5. 7profit += 0 = 0日差是负的，这天不操作（空仓），profit 加 0、保持 0。这就是负例：下跌日一律跳过，灰掉表示没吃进。
6. 8diff = 5 − 1 = +4走到第 3 天（价 5），算差：5 − 1 = +4，第一次出现正的涨幅。
7. 9profit += 4 = 4日差为正，把这 4 块吃进口袋：profit 累计到 4。绿色标出的 1 和 5 就是这一段「昨天买、今天卖」赚到的钱。
8. 10diff = 3 − 5 = −2走到第 4 天（价 3），算差：3 − 5 = −2，又是负的。
9. 11profit += 0 = 4下跌日再次跳过，profit 不动，仍是 4。注意这里没有去「找谷底找峰顶」——只看相邻两天的正负就够了。
10. 12diff = 6 − 3 = +3走到第 5 天（价 6），算差：6 − 3 = +3，又一段上涨。
11. 13profit += 3 = 7正差再吃下 3 块：profit 从 4 累到 7。绿色的 3 和 6 是这第二段赚到的钱。
12. 14profit += 0 = 7最后一天 6 → 4 又是跌，跳过。全程只把两段正涨幅累加：4 + 3 = 7，就是答案。
13. 17一段连续上涨（如 1→5）拆成每天的差，求和不变；下跌日加 0 不亏。所以「每个正的日差都拿」就等于全局最优——这就是贪心在这题成立的根本原因。

⚠️ 容易写错的地方

完整代码（Python）

class Solution:
    def maxProfit(self, prices):
        ans = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                ans += prices[i] - prices[i - 1]
        return ans

# 「操作次数不限、收益可分段独立」的贪心都套
total = 0
for i in range(1, n):
    gain = 收益(i - 1, i)
    if gain > 0: total += gain            # 只累加正收益
return total

复杂度

面试官可能追问