贪心 · 交换论证与反悔贪心

1. 核心原理

贪心算法（greedy algorithm）针对一类带最优目标 + 局部决策的问题：在每一步从一组候选里选"当下看起来最好"的那一个，希望最终累加得到全局最优。它的代码总是很短——sort 一下加一个循环、或者一个堆扫一遍——但正确性证明从来不是显然的。

和动态规划的对比：DP 枚举所有子问题的最优解，几乎一定对，但状态数多；贪心是 DP 的特例，省掉了枚举，前提是"当下最好"恰好和"全局最好"对齐。如果对不齐，贪心给出错答案而不会报错。所以贪心的可信度完全建立在正确性证明上。

本章关注两种最常用的证明工具：交换论证（exchange argument）和反悔贪心（regret heap）。前者适合"一次性看到全部输入、能预先排序"的场景，后者适合"输入按时间 / 位置流入、约束滚动出现"的场景。

交换论证

交换论证的标准套路：假设有一个最优解 OPT，它和贪心解 GREEDY 不完全相同。找出两者的第一个差异位置，把 OPT 在这个位置上的选择换成 GREEDY 的选择，证明两件事：

1. 换完后仍然合法（不违反任何约束）
2. 换完后不会变差（目标函数 ≥ 原 OPT）

如果两条都成立，OPT 经过有限次交换可以变成 GREEDY，且每一步都不变差——所以 GREEDY 本身就是最优解。

最经典的子类型是邻位交换论证：只考虑"相邻两个位置交换"。给定排好序的序列 s[0] ≤ s[1] ≤ ... ≤ s[n-1]，若存在某种排列使目标值更大，则其中必有一对相邻元素 (s[i], s[i+1]) 满足"交换它们能让目标值变大"。证明 GREEDY 排序下任意相邻对都不可被交换变好，等价于 GREEDY 是最优。

交换论证适合的题：

• 排序 + 贪心：按某个 key 排序后，前缀 / 后缀 / 区间选取（LC 1402, 1029, 1383）
• 数对比较：相邻两个元素的相对位置可以独立判断（LC 179, 1387）

写交换论证时一个常见错误：只证了"局部交换不变差"，忘了交换后仍需合法。LC 1402 没有约束，所以任何排列都合法；但调度题、区间题里，交换可能破坏约束。两件事都要证。

反悔贪心

交换论证依赖"能一次性看到全部输入并排序"。但有些题的约束只在过程中暴露——汽车加油站按位置先后给出，到了某站才决定加不加；选课的截止日各不相同，没法一刀切排序。这类题用反悔贪心：

1. 按某种次序处理输入（位置 / 时间 / 截止日 / 优先级）。
2. 能选就选，把当前选项放进堆里维护。
3. 违反约束时，从堆里反悔最差的那个——撤销过去某次决策，换成当前的决策（或干脆丢掉当前）。

之前的选择不是不可变的：发现选错了，可以撤销腾出位置。最大堆 / 最小堆是反悔的天然工具，O(log n) 找出"已选里最差的"。

反悔贪心有两种常见模式：

两套工具的分工

通用原则：先排序、再扫一遍是 default；扫不动（约束在过程中变化）就上堆 + 反悔。

2. 通用模板

排序 + 后缀贪心是交换论证最常见的代码骨架，下面给三语言模板。母题 LC 1402（§3）就是直接应用。反悔贪心的两种模式骨架附在最后。

class Solution:
    def maxSatisfaction(self, satisfaction: list[int]) -> int:
        satisfaction.sort()                           # 1. 排序（升序）
        ans = 0
        suffix_sum = 0
        # 2. 从右往左累加：每加入一个元素，等价于把它放到已选集合最前面
        for x in reversed(satisfaction):
            if suffix_sum + x < 0:
                break                                 # 3. 加完会亏，停（后续只会更亏）
            suffix_sum += x
            ans += suffix_sum                         # 4. 新答案 = 旧答案 + 新后缀和
        return ans

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);                              // 1. 排序（升序）
        int ans = 0, suffixSum = 0;
        // 2. 从右往左累加
        for (int i = satisfaction.length - 1; i >= 0; i--) {
            if (suffixSum + satisfaction[i] < 0) break;         // 3. 再加就亏，停
            suffixSum += satisfaction[i];
            ans += suffixSum;                                   // 4. 累加新后缀和
        }
        return ans;
    }
}

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());         // 1. 排序（升序）
        int ans = 0, suffixSum = 0;
        // 2. 从右往左累加
        for (int i = satisfaction.size() - 1; i >= 0; i--) {
            if (suffixSum + satisfaction[i] < 0) break;         // 3. 再加就亏，停
            suffixSum += satisfaction[i];
            ans += suffixSum;                                   // 4. 累加新后缀和
        }
        return ans;
    }
};

复杂度：时间 O(n log n) 排序主导，空间 O(1) 原地排序 + 两个累加变量。

模板要点：

• 排序方向决定累加方向：升序排好后从右往左累加（大的先入），等价于"按降序贡献越来越大的位置系数"。降序排则从左往右累加，本质等价。
• ans += suffix_sum 的含义：在已选集合最前面再插入一道菜，等价于已选每道菜系数 +1、新菜系数为 1，所以新答案 = 旧答案 + (旧后缀和 + 新菜) = 旧答案 + 新后缀和。
• 停止条件 suffix_sum + x < 0：后缀和一旦变非正，再往前加只会越加越亏（前面元素更小，加进来后缀和更负）。提前 break 不影响正确性。
• ans 初始 0 对应"一道菜都不选"——题目允许空选。所有元素全为负时，第一次循环就 break，返回 0。

反悔贪心通用骨架（两种模式合一）：

def regret_greedy(items):
    items.sort(key=lambda x: x.sort_key)        # 1. 按某个 key 排序
    heap = []                                    # 候选池 / 已选池
    state = ...                                  # 当前累计状态（time / fuel / profit）

    for item in items:
        # 模式 A — "换"：先无脑选，违约时换掉最差的
        push_to_heap(heap, item)
        state = update(state, item)
        while violates_constraint(state):
            worst = pop_worst(heap)              # 堆顶维护"最差"
            state = revoke(state, worst)         # 反悔：撤销贡献

        # 模式 B — "补"：先压入候选池，需要时再补
        push_to_pool(heap, item)
        if needs_more(state):
            best = pop_best(heap)                # 堆顶维护"最优可补"
            state = apply(state, best)

    return collect_answer(heap, state)

模式 A 的典型是 LC 630（换最长课），模式 B 的典型是 LC 871（补最大油量），§4.2 / 4.3 各展开一遍。

3. 母题精讲

LeetCode 1402. Reducing Dishes

链接：LeetCode 1402

题意：厨师有一组菜 satisfaction[i] 表示第 i 道菜的"满意度"，可以是正可以是负。厨师可以任选一个子集，并自己决定上菜顺序。一道菜在第 t 个位置上桌（t 从 1 开始数），它的贡献是 satisfaction[i] × t。求所有可能选法 + 排列方式中"喜欢之和"的最大值。

数据范围：

• n = satisfaction.length：1 到 500
• satisfaction[i]：−1000 到 1000

示例：

输入：satisfaction = [-1, -8, 0, 5, -9]
输出：14
解释：去掉 -8、-9 不上，剩下排成 [-1, 0, 5]，
     喜欢之和 = -1 × 1 + 0 × 2 + 5 × 3 = -1 + 0 + 15 = 14。

暴力思路：枚举子集 + 全排列

最朴素的写法：枚举所有子集（2ⁿ），对每个子集枚举所有排列（k!），求 max。n = 500 时根本跑不动——2⁵⁰⁰ 直接爆。

但这个暴力告诉我们一件事：给定一个被选中的菜的集合，最优顺序是什么？

直觉上，越后面的位置乘的系数 t 越大，所以满意度高的菜应该排在后面。换句话说，选中的菜按满意度升序排好就行——最大的菜乘最大的系数。

证明（邻位交换论证）：假设两道相邻菜 A、B 满意度满足 a ≤ b，放在第 t 位和 t+1 位。

• 现状（a 在前 b 在后）：a × t + b × (t + 1) = at + bt + b
• 交换（b 在前 a 在后）：b × t + a × (t + 1) = bt + at + a
• 差 = 现状 − 交换 = b − a ≥ 0

所以"小的在前，大的在后"不亏。

再问一步：哪些菜该被选？

把所有菜按满意度升序排好，假设排完是 s[0] ≤ s[1] ≤ ... ≤ s[n-1]。要选一个后缀 s[k], s[k+1], ..., s[n-1]（一定是后缀，因为越大的越值得选 + 越值得排后面）。

为什么一定是后缀？假设当前选的 k 道菜贡献 s[i₁] × 1 + ... + s[i_k] × k。若存在 i < j，s[i] 被选而 s[j] 没被选（注意 s[i] ≤ s[j]），把 s[j] 接到末尾，新答案 = 原答案 + s[j] × (k + 1)。只要这个增量 ≥ 0 就值得加，反之不加。

反过来用：从右往左累加，只要总贡献还在涨，就继续加。一旦某次加完反而变小，停。

排序后  s[0]  s[1]  s[2]  ...  s[n-1]
        ↑                       ↑
       小                       大

从右往左：先加 s[n-1]，再 s[n-2]，... 同时维护后缀和与答案。

代码就是 §2 的模板。复杂度：排序 O(n log n) + 扫描 O(n)，总 O(n log n)。

4. 例题（三道）

按"证明难度递增"排：先回到母题做易错点回收（LC 1402），再用堆做反悔贪心（LC 871），最后是反悔贪心的进阶变体（LC 630）。

4.1 LC 1402 做菜顺序回头看

题目链接。题面见 §3。代码就是 §2 的模板。两个常踩的易错点：

• 停止条件用 suffix_sum + x < 0 而不是 x < 0。一个孤立的负数菜可能值得加——只要它之后还有更大的正数把它扛起来。例如 [-1, 5]，加 -1 后 suffix_sum = 4，仍然为正，不该停。
• ans = 0 初始化对应"一道菜都不选"。题目允许空选。所有菜都是负数时 suffix_sum + x < 0 在第一次就触发 break，直接返回 0。

Follow-up：上面是离线题——所有菜一次给齐可以排序。如果输入是"流式"的，比如开车经过一连串加油站，到了就必须决定加不加，怎么办？

4.2 LC 871 最低加油次数

链接：LeetCode 871

题意：一辆车从起点开到目标点，距离 target 英里。车初始有 startFuel 升油，每升油可以开 1 英里。沿路有 n 个加油站，stations[i] = [position, fuel] 表示位置和油量。问最少加几次油才能到目标；不能到目标返回 -1。

数据范围：

• target：1 到 10⁹
• startFuel：0 到 10⁹
• n = stations.length：0 到 500
• 油站按位置升序给出，位置严格递增

示例：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
  从 0 出发，10 升油可以开到位置 10。
  在位置 10 加 60 升 → 油量 60，可以开到位置 70。
  到位置 60 时加 40 升 → 油量从 (60 - 50) = 10 升到 50 升，能到位置 110 > 100。
  共加油 2 次。

朴素思路：DP

设 f[i][k] = 经过前 i 个油站、加了 k 次油，最远能开到哪里。状态转移 O(n²)：

f[i][k] = max(
    f[i - 1][k],                      // 不在第 i 个油站加
    f[i - 1][k - 1] + stations[i][1]  // 在第 i 个加（前提：f[i-1][k-1] >= stations[i][0]）
)

复杂度 O(n²)，n = 500 能过。但有更"贪"的写法。

反悔贪心：先开过再说，缺油就回去最大的加油站加

直觉：每次开过一个加油站，我们不立刻决定要不要加，而是把它放进一个"候选"堆里。一直开，开到油不够、过不去下一个站（或到不了终点）时，从堆里挑油量最大的那个站"反悔加油"——相当于把"过去经过的某个油站补加上"。

关键不变量：

走到当前位置 pos，我们记录目前为止经过的所有油站的油量，存在一个最大堆里。当油不够开到下一站 / 终点时，从堆里弹出最大油量补上。如果堆空了还是不够，回 -1。

这等价于"按顺序处理油站，能选就选，过约束（开不到下一站）时反悔加最大的"。最大堆是反悔的天然结构——O(log n) 弹最大。

import heapq

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: list[list[int]]) -> int:
        # 加一个 [target, 0] 哨兵，把"到达终点"也当成最后一站
        stations = stations + [[target, 0]]
        heap = []                                     # 最大堆（用负数模拟）
        fuel = startFuel
        prev_pos = 0
        ans = 0
        for pos, fuel_at in stations:
            # 开到当前站需要 (pos - prev_pos) 升油
            fuel -= (pos - prev_pos)
            # 不够就从堆里"反悔加油"
            while fuel < 0 and heap:
                fuel += -heapq.heappop(heap)          # 弹出最大油量
                ans += 1
            if fuel < 0:
                return -1                             # 堆空了还是不够
            heapq.heappush(heap, -fuel_at)
            prev_pos = pos
        return ans

逐行讲：

• 加哨兵 [target, 0]：让循环统一处理"到达终点"——到目标点视作一个油量为 0 的虚拟站。这样可以避免"循环结束后还要单独判一次能不能到 target"。
• heap 存负油量：Python heapq 是最小堆，存负数 = 最大堆。-heapq.heappop(heap) 弹出实际最大油量。
• fuel -= (pos - prev_pos)：从上一站开到当前位置消耗这么多油。可能变负——意味着光靠之前积累的油到不了，需要反悔加油。
• while fuel < 0 and heap：每次反悔加最大油量。可能要加多次（堆里前几大都不够）。
• if fuel < 0: return -1：堆空了油还不够，不可能到。
• heapq.heappush(heap, -fuel_at)：开过当前站，把它的油量入堆。注意是开过之后入堆——确保"反悔加油"不会反悔到一个还没经过的站。

为什么这样贪心是对的？

交换论证：假设最优解在某些站加了油总次数 k，我们的贪心方案加了 k'。要证 k' ≤ k。

考虑最优解 OPT 走到第 j 步时，假设它加的某些站 S 和贪心解加的某些站 G 不完全相同。在某个最早出现差异的点：如果 OPT 加了 a，贪心加了 b（b 是堆里油量最大的），按贪心选法 fuel_b ≥ fuel_a。把 OPT 改成加 b——油量不会减少，所以后续路径仍然可达，加油次数不变。一连串交换之后 OPT 变成贪心。所以贪心解的加油次数 = 最优。

复杂度：每个站至多入堆一次出堆一次，加上反悔时的弹出，总 O(n log n)。空间 O(n) 堆。

Follow-up：上面"反悔"是把过去某个站"补加"。如果不同的选项之间还有容量约束（比如不只是数次数，而是有时间窗口要求），反悔从"补加最大"变成"替换最差"。

4.3 LC 630 课程表 III

链接：LeetCode 630

题意：有 n 门课，每门 courses[i] = [duration, lastDay] 表示这门课持续多少天、必须在第几天之前（含）结束。你从第 1 天开始，一次只能上一门课。求最多能修完几门。

数据范围：

• n = courses.length：1 到 10⁴
• duration, lastDay：1 到 10⁴

示例：

输入：courses = [[100,200], [200,1300], [1000,1250], [2000,3200]]
输出：3
解释：能修完 1, 2, 3 门课，但 4 门不行。
  按截止日 200, 1250, 1300, 3200 排序后看：
  课 1 占用第 1~100 天 (结束在 100 ≤ 200，OK)
  课 3 占用第 101~1100 天 (结束在 1100 ≤ 1250，OK)
  课 2 占用第 1101~1300 天 (结束在 1300 ≤ 1300，OK)
  课 4 需要 2000 天，无法在 3200 之前从第 1301 天开始（1301 + 2000 = 3301 > 3200），放弃。
  共 3 门。

反悔贪心：按截止日排序，超时就反悔最长那门

第一步：先按 lastDay 升序排序——截止日早的先考虑（不然来不及）。

第二步：维护"已选课"的最大堆，按 duration 比较。维护"当前时间" time。对每门课 (duration, lastDay)：

• 如果 time + duration ≤ lastDay：直接选上，time += duration，入堆。
• 否则（来不及）：看堆顶——已选课里最长的那门。如果 当前课 duration < 堆顶 duration，反悔：把堆顶弹出（不上那门长课了），把当前课加入。time -= 堆顶 duration; time += duration。如果当前课比堆里所有都长，跳过（反悔也没用）。

为什么这么贪是对的？

直觉：要修最多门课，等价于"在每个时间点之前完成的课的总耗时尽量小"。所以遇到一门"装不下"的课时，如果它比当前已选里最长的还短，换掉它能让总耗时变小，未来能容纳更多课。

正式证明（交换论证）：

假设最优解修了 OPT 门课。按截止日升序处理课程，第 i 步贪心维护的"已选集合" G 包含 g 门课，总耗时 T_g。 引理：g ≥ |OPT 在前 i 门里选的课数|，且 T_g ≤ OPT 对应的最小总耗时。

归纳：第 i 步如果 G 选了新课，新总耗时增加了 duration_i；如果反悔（替换最长），新总耗时减少（因为新课更短）。两种情况下 G 的"门数"和"总耗时"都至少和 OPT 的最优选择一样好。

import heapq

class Solution:
    def scheduleCourse(self, courses: list[list[int]]) -> int:
        # 按截止日升序
        courses.sort(key=lambda c: c[1])
        heap = []                                     # 最大堆（存负数）维护已选课的 duration
        time = 0
        for duration, lastDay in courses:
            if time + duration <= lastDay:
                heapq.heappush(heap, -duration)
                time += duration
            elif heap and -heap[0] > duration:
                # 反悔：把最长那门换掉
                time += duration - (-heapq.heappop(heap))
                heapq.heappush(heap, -duration)
        return len(heap)

逐行讲：

• courses.sort(key=lambda c: c[1])：按 lastDay 升序排序——这是反悔贪心的"输入排序"步骤。
• time + duration <= lastDay：能装下，直接选。time 累加，入堆（堆里存负 duration）。
• elif heap and -heap[0] > duration：装不下，但当前课比堆顶（已选里最长）还短。反悔——弹堆顶，入当前课。注意：反悔之后总课数不变，但总耗时下降，所以 time 更新为 time + 当前 duration - 堆顶 duration。
• return len(heap)：堆里有多少课就是答案。

复杂度：排序 O(n log n) + 每门课至多入堆、出堆各一次 O(n log n)。总 O(n log n)。空间 O(n)。

反悔贪心的两种模式对比

两者结构一致——都是堆 + "违约则替换"。区别在于：

• LC 871 反悔是"补"（加进来），堆是"未选但已遇到"的池子。
• LC 630 反悔是"换"（替换已选），堆是"已选"的池子。

反悔贪心通用骨架

把上面两种模式抽出一个统一伪代码：

def regret_greedy(items):
    items.sort(key=lambda x: x.sort_key)        # 1. 按某个 key 排序（截止日 / 出现顺序）
    heap = []                                    # 可选 / 已选 池
    state = ...                                  # 当前累计状态（time、fuel、profit ...）

    for item in items:
        # 模式 A — "换"：先无脑选，违约时换掉最差的
        push_to_heap(heap, item)
        state = update(state, item)
        while violates_constraint(state):
            worst = pop_worst(heap)              # 用堆顶维护"最差"
            state = revoke(state, worst)         # 反悔：撤销贡献

        # 模式 B — "补"：先压入候选池，需要时再补
        push_to_pool(heap, item)
        if needs_more(state):
            best = pop_best(heap)                # 用堆顶维护"最优可补"
            state = apply(state, best)
            if heap_empty_and_still_need:
                return -1                        # 无解

    return collect_answer(heap, state)

记忆要点：

• 排序 key 决定遍历顺序（截止日早 / 距离近 / 优先级高）
• 堆维护"待反悔候选"（已选最差 or 已遇到最优）
• 触发条件就是约束违约或目标未达
• 反悔操作 = 撤销 + 替换

记住这套骨架能 cover 90% 的反悔贪心题——LC 1383 表演者评分、LC 502 IPO、LC 253 会议室 II 都是变体。

5. 边界、易错与复杂度

交换论证别忽略约束

写交换论证时常见的错误：只证了"局部交换不变差"，忘记了交换后仍然合法。LC 1402 没约束，所以怎么排都合法。但区间题 / 调度题里，交换可能破坏某个约束。一定要两件事都证：

• 交换不变差（目标函数 ≥）
• 交换后仍合法（不违反任何约束）

反悔贪心的初始排序很关键

反悔贪心几乎都要"先按某个 key 排序"再扫描。排错 key 就全错：

• LC 871 油站本身已按位置升序——这是物理顺序，不能动。
• LC 630 按 lastDay 升序——按 duration 排会错。
• LC 502 IPO（§6）按 capital 升序，再按 profit 维护最大堆。

如果一道题需要反悔贪心但不知道按什么排，常见尝试：截止日、起始时间、容量、利润。

Python / Java / Go 最大堆

Python heapq 是最小堆，存负数模拟最大堆即可：heapq.heappush(heap, -x)，弹出 -heapq.heappop(heap)。Java 用 new PriorityQueue<>(Comparator.reverseOrder())。Go 没原生最大堆，自己实现 heap.Interface 并把 Less 反过来写。

反悔时 time 别加错

LC 630 反悔时 time += duration - (-heapq.heappop(heap)) 容易写错符号。-heapq.heappop(heap) 是弹出的实际值（正数）。time 减去这个值（移除最长课）再加上新 duration，最终增量 = duration - 弹出值，是负数（因为弹出值更大）。

写代码时建议先拆开：

old_max = -heapq.heappop(heap)
time = time - old_max + duration
heapq.heappush(heap, -duration)

清晰、不容易出错。

1402 答案能否为负

不能。代码初始 ans = 0，对应"一道菜都不选"。所有菜都是负数时 suffix_sum + x < 0 在第一次就触发 break，直接返回 0。

复杂度速查

反悔贪心三道变体题的常见坑

变体题在面试 follow-up 里高频出现，每道都有一个容易翻车的边界：

• LC 1383 最大的团队表现值：性能 × 效率最小值 = 团队表现。按效率降序排，扫到第 i 个时当前 efficiency 是整团最小值。MOD = 10⁹ + 7 的取模时机要小心——total * eff 这一步必须先取模再乘，否则 long 也会溢出（性能上界 1e7 × n 上界 1e5 × eff 上界 1e9 ≈ 1e21，long 装不下）。

• LC 502 IPO：双堆（项目 hold + 项目 do），按 capital 解锁后入"可做"大顶堆。当前买不起且堆空时立刻 break——后面的项目 capital 单调增，堆又空，永远凑不出钱。少这一行会 TLE，看似无限循环。

• LC 253 会议室 II：按 start 排序后堆维护"在用的会议室结束时间"。tie-break：同时刻一个 end 一个 start 时，按"先 end 后 start"处理（end 优先弹出释放房间）—— 否则会算多一间。Python 用 (time, type_priority) 元组，end 标 0 / start 标 1 让排序自动处理。

记忆要点：mod 乘法时机（LC 1383）、堆空 break（LC 502）、tie-break 顺序（LC 253）——三条都是变体题里"小改动让你 WA 或 TLE"的常见来源。

7. 小结

贪心算法的代码总是很短——sort 一下加一个循环、或者一个堆扫一遍。但正确性证明从来不平凡。本章两件证明工具：

• 交换论证：假设有最优解 OPT，找一个差异位置把 OPT 换成贪心，证明换完不亏。LC 1402 / 1029 是"全离线"——所有输入一次给齐，排序后扫一遍。
• 反悔贪心 + 堆：流式输入、约束在过程中出现。O(log n) 维护"已选池"，违反约束时弹出最差的换上当前。LC 871 / 630 / 502 都是这套。

工程取舍：

• 输入能一次性看到全部 + 有自然排序 key → 排序 + 一次扫描（交换论证证明）
• 输入按时间 / 位置流入 + 约束滚动出现 → 堆 + 反悔贪心
• 想不出贪心策略 → 退回 DP（贪心是 DP 的特例，DP 几乎总能 work，只是慢一些）

下一节会进入贪心的"字典序"专题——LC 316 去除重复字母、LC 402 移掉 k 位数字、LC 738 单调递增的数字。字典序题的核心也是交换论证，但比较的是"位级 vs 位级"而不是"值 vs 值"。

对应灵神题单：贪心 · 反悔 / 交换论证

进一步阅读：灵茶山艾府《贪心题单》；LeetCode Greedy 标签 高频题