买卖股票的最佳时机 II 如何用贪心求最大利润？（LeetCode 122）

简化版

给每天的股价 prices[]，你可以多次买卖（但手上最多持有一股，必须先卖再买），求能获得的最大总利润。贪心策略极简：把所有「上坡」的利润都收进口袋——只要今天比昨天贵（prices[i] > prices[i-1]），就把这段差价 prices[i]-prices[i-1] 累加进结果。所有相邻上涨的差价之和，就是最大利润。

详细版

int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];   // 吃下每一段上涨
        }
    }
    return profit;
}

策略：把整条价格曲线拆成一段段单调上涨和下跌，只赚上涨段，跌段不参与（不买）。
等价理解：一段连续上涨 a→b→c（a<b<c）的总收益 (b-a)+(c-b) = c-a，和「a 买 c 卖」完全相等——所以按天累加上坡差价，等于低买高卖每一段涨幅。
前提：允许无限次交易、无手续费。有手续费或限制次数就得用 DP。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、题目的关键约束：无限次交易

这题和「买卖股票 I（只能买卖一次）」的区别是——可以买卖任意多次（同一天可以先卖再买）。正是「无限次」这个宽松条件，让贪心成为可能：既然次数不限，我就可以把每一小段涨幅都单独吃下来。

“无限次”仍受不能同时持有多股约束：必须先卖出才能再次买入。但在同一天按同一价格卖出再买入不会改变现金，所以把一段上涨拆成每日正差与只在谷底买、峰顶卖利润相同。

二、贪心核心：只吃上坡

把价格画成折线图，它由若干上升段和下降段交替组成。要利润最大：

上升段：低点买、高点卖，赚这段涨幅。
下降段：不持有（不买），避免亏损。

而一段连续上升 p0 < p1 < p2 < ... < pk，你可以「p0 买、pk 卖」一次赚 pk - p0，也可以「每天买了第二天卖」赚 (p1-p0)+(p2-p1)+...+(pk-p{k-1})，两者数值完全相等（中间项抵消）。所以代码里「累加所有相邻正差价」等价于「抓住每一段完整涨幅」。

这就是为什么一行 if (prices[i] > prices[i-1]) profit += 差价 就够了——它自动把连续上涨拼成整段收益，把下跌自动跳过。

三、贪心正确性

为什么「累加所有正的相邻差价」就是全局最优？

它是利润的上界：任何交易方案的总利润，都可以分解到「相邻两天」的价格变动上。你能赚到的，最多就是所有上涨日贡献的正差价之和；下跌日无论如何操作都不可能贡献正收益（你不会在会跌的时候持有）。
它可达：上面的「每段低买高卖」策略确实能实现这个上界。

上界可达 ⇒ 贪心解就是最优解。

四、和动态规划的对照（推荐一起掌握）

这题也能用状态机 DP解，且 DP 是能推广到「有手续费 / 限交易次数 / 含冷冻期」的通法：

int maxProfit(int[] prices) {
    int hold = -prices[0];   // 持有一股时的最大现金
    int cash = 0;            // 空仓时的最大现金
    for (int i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i]);   // 今天卖 or 继续空仓
        hold = Math.max(hold, cash - prices[i]);   // 今天买 or 继续持有
    }
    return cash;   // 最后一定空仓收益最大
}

两个状态：cash（今天结束时空仓的最大收益）、hold（今天结束时持有一股的最大收益）。
无限次交易时，这个 DP 的结果和贪心完全一致；但一旦加「最多 k 次」「手续费 fee」「冷冻期」，贪心失效，只能靠这套状态机扩展。

面试建议：先给贪心（简洁惊艳），再补一句「如果加手续费/限次数，我会用状态机 DP」，展示你知道贪心的边界。

五、常见坑

坑 1：以为要找全局最低点买、最高点卖。那是「只能交易一次」的 I 题。本题多次交易，逐段吃涨幅更优。
坑 2：同一天不能同时持有多股。贪心天然满足（每段独立），不必担心。
坑 3：有手续费还硬套贪心。加了 fee 后，小涨幅可能覆盖不了手续费，得权衡——必须上 DP。

六、贪心选择为什么不会堵死未来

本题每一步选择是：无限次交易且不能同时持股时，把每个正相邻价差都计入利润。

正确性不能只靠直觉，核心证明是：任意上升段 p[l]→p[r] 的利润等于沿途所有正差之和，拆成多次交易不损失且可避开下降。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：[7,1,5,3,6,4] 收益 (5-1)+(6-3)=7。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：一次交易、手续费、冷冻期或限 k 次时不能直接累加正差；同日卖买在该模型下等价允许。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：应寻找最低买入和最高卖出的一次交易。 本题允许多次交易。
误区：下降段也应持有等待反弹。 卖出再低价买回不会更差。
误区：有手续费仍累加所有正差。 频繁交易会重复付费，需要 DP 或合并上涨段。
追问：为什么拆分上涨段不亏？ 差值可望远镜求和。
追问：和两状态 DP 的关系？ 贪心是无限次无额外约束 DP 的化简。
追问：同一天能否卖后再买？ 不同时持有多股且价格相同，数学上不影响利润。

九、加强记忆

买卖股票 II（无限次交易）= 贪心吃下每一段上坡：prices[i] > prices[i-1] 就把差价累加，所有相邻正差价之和即最大利润。原理是连续上涨段「每天买卖」与「整段低买高卖」收益相等，且正差价之和是利润上界又可达，故最优。前提是无限次、无手续费；一旦限次数/加手续费/含冷冻期，改用 cash/hold 状态机 DP（无限次时两者结果一致）。

简化版

详细版