反悔贪心专题 (Regret Greedy with Priority Queue)

反悔贪心（Regret Greedy） 是贪心算法中最具技巧性与实战威力的高阶分支。

普通贪心严格遵循“一旦做出决策，绝不回头”的原则，这要求当前决策必须具备绝对的无后效性。

然而，在许多复杂约束问题中，局部最优并不保证全局最优。此时，反悔贪心的哲学是：

“当前能选就先选上（贪心尝试）；当后续遇到更优的选项导致资源超标时，从历史已选集合中挑出最劣的那个‘反悔’并替换掉（利用优先队列在 \(\mathcal{O}(\log N)\) 内撤销决策）。”

flowchart TD
    A["遍历当前元素 x"] --> B{"当前预算/时间是否充足?"}
    B -- 充足 --> C["贪心纳入已选集合, 压入优先队列"]
    B -- 超标 --> D{"优先队列堆顶最劣项 vs 当前项 x"}
    D -- 当前项更优 --> E["触发反悔: 弹出堆顶最劣项, 换入当前项 x, 释放资源差额"]
    D -- 历史项更好 --> F["放弃当前项 x, 保持历史集合"]

---

1. 经典模型一：截止时间约束下的最大选课数 (LeetCode 630)

1.1 问题定义

给定 \(n\) 门课程，每门课程有两个参数：持续时间 \(t_i\) 和最晚截止时间 \(d_i\)。必须在不超过截止时间的前提下完成课程，求最多能修多少门课。

1.2 为什么普通贪心失效？

• 策略 A（贪心按截止时间排序，能修就修）：可能会因为修了一门耗时极长（如持续 100 天）但截止很早的课，导致后面多门耗时很短的课无法修读；
• 策略 B（贪心按持续时间排序，选耗时短的）：可能会因为先修了耗时短但截止很晚的课，导致紧迫的早截止课程直接超时。

1.3 反悔贪心解决方案与证明

1. 基础排序（锚定紧迫性基准）：必须先按截止时间 \(d_i\) 升序排序；
2. 贪心选择 + 大顶堆反悔：
3. 维护当前已消耗的总时间 \(total\_time\) 和已修课程耗时的大顶堆 priority_queue<int> max_heap；
4. 遍历每门课程 \((t_i, d_i)\)：
   • 若 \(total\_time + t_i \le d_i\)：时间充足，直接修，total_time += t_i，max_heap.push(t_i)；
   • 若 \(total\_time + t_i > d_i\)：超期了！但若堆顶的最大耗时比当前课程更大（max_heap.top() > t_i），说明我们可以反悔修堆顶那门课，改为修当前这门课！
5. 正确性证明（势能与不变量）：
6. 当用 \(t_i\) 替换堆顶 \(top\) 时，已修课程的总门数完全保持不变；
7. 但 \(total\_time\) 净减少了 \(top - t_i > 0\)！
8. 既然总耗时变少了，而后续课程的截止时间只会更晚（因为已排好序），这个替换操作使得留给未来所有课程的时间预算绝对变宽裕了，因此该反悔操作必定是严格不劣的！

#include <vector>
#include <queue>
#include <algorithm>

int scheduleCourse(std::vector<std::vector<int>>& courses) {
    // 1. 按截止时间升序排序
    std::sort(courses.begin(), courses.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });

    std::priority_queue<int> max_heap; // 大顶堆存储已修课程的持续时间
    int total_time = 0;

    for (const auto& c : courses) {
        int duration = c[0];
        int last_day = c[1];

        if (total_time + duration <= last_day) {
            total_time += duration;
            max_heap.push(duration);
        } else if (!max_heap.empty() && max_heap.top() > duration) {
            // 反悔机制: 剔除历史上耗时最长的那门课, 换入耗时更短的当前课
            total_time -= max_heap.top();
            max_heap.pop();
            total_time += duration;
            max_heap.push(duration);
        }
    }
    return static_cast<int>(max_heap.size());
}

---

2. 经典模型二：最低加油次数 (LeetCode 871)

2.1 问题定义

汽车从位置 0 出发前往距离为 \(target\) 的目的地，初始油量为 \(startFuel\)。沿途有若干加油站，求到达目的地所需的最少加油次数。若无法到达返回 \(-1\)。

2.2 反悔贪心机制

• 直觉：沿途路过加油站时，并不急于立即加油（因为每次加油都计入加油次数，加了不一定用得上）；
• 虚拟反悔：
• 只要当前油量还能往前开，就把沿途路过的所有加油站的储油量扔进大顶堆中（将其视为随车携带但尚未使用的“备用加油券”）；
• 当油量不足以支撑开到下一个加油站（或目的地）时，必须被迫加油。此时从大顶堆中贪心取出储油量最大的加油站进行“虚拟反悔补油”，加油次数累加 1；
• 若大顶堆已空仍无法到达下一站，说明穷尽所有加油站依然无法前进，返回 \(-1\)。

#include <vector>
#include <queue>

int minRefuelStops(int target, int startFuel, std::vector<std::vector<int>>& stations) {
    std::priority_queue<int> max_heap; // 存储路过加油站的油量
    long long curr_fuel = startFuel;
    int stops = 0;
    size_t idx = 0;
    size_t n = stations.size();

    while (curr_fuel < target) {
        // 将所有当前油量能够到达的加油站入堆
        while (idx < n && stations[idx][0] <= curr_fuel) {
            max_heap.push(stations[idx][1]);
            idx++;
        }

        // 若没有可用的加油站, 说明无法继续前进
        if (max_heap.empty()) return -1;

        // 反悔贪心: 取出历史油量最大的加油站加油
        curr_fuel += max_heap.top();
        max_heap.pop();
        stops++;
    }
    return stops;
}

---

3. 经典模型三：股票买卖与反悔交易 (CF 865D / Buy Low Sell High)

问题：给定每天的股票价格，每天可以买入一股、卖出一股或不操作。求无限次交易下的最大利润。

反悔贪心建模：

• 维护一个小顶堆 min_heap 记录历史买入价格；
• 遍历第 \(i\) 天的价格 \(P_i\)：
• 若堆非空且堆顶 \(min\_heap.top() < P_i\)：
  • 当前存在套利空间：利润累加 \(P_i - min\_heap.top()\)；
  • 弹出堆顶，并将 \(P_i\) 压入堆两次！
  • 为什么压入两次？
  • 第一次压入代表：今天卖出了堆顶股票，同时留下一张以价格 \(P_i\) 买入该股票的“反悔凭证”；如果未来某天价格 \(P_j > P_i\)，未来可以反悔今天在 \(P_i\) 卖出的决策，改为在 \(P_j\) 卖出（因为 \((P_i - top) + (P_j - P_i) = P_j - top\)）！
  • 第二次压入代表：今天也可以作为一个独立的买入日。

---

4. LeetCode 经典真题精选与深度精析

• LeetCode 630 - 课程表 III (Course Schedule III) 困难

  提示

  反悔贪心天花板（大顶堆维护已修课程）。

  • 详见本文第 1 节完整推导。
  • 必须先按截止时间升序排序；若超时，用大顶堆淘汰耗时最长课，优化时间预算。
  • 时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(N)\)。

• LeetCode 871 - 最低加油次数 (Minimum Number of Refueling Stops) 困难

  提示

  路过暂存备选 + 缺油反悔补油（大顶堆）。

  • 详见本文第 2 节完整推导。
  • 沿途加油站放入大顶堆，油量不足时贪心补最大的油。
  • 时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(N)\)。

• LeetCode 1642 - 可以到达的最远建筑 (Furthest Building You Can Reach) 中等

  提示

  反悔贪心梯子与砖块选择（小顶堆）。

  • 梯子可以跨越任意高度差，砖块只能按高度差逐个消耗。
  • 贪心策略：梯子应该用在高度差最大的跨越上！
  • 维护一个小顶堆存储所有已跨越的高度差。优先使用梯子跨越，并将高度差放入小顶堆。
  • 当使用梯子的次数超过梯子总数 \(ladders\) 时，说明梯子不够用了，从小顶堆中弹出最小的高度差，将其改为使用砖块支付；
  • 若剩余砖块总数 \(< 0\)，说明砖块耗尽且梯子无法顶替，当前位置即为能到达的最远建筑。
  • 时间复杂度 \(\mathcal{O}(N \log L)\)，其中 \(L\) 为梯子数量。

• LeetCode 2813 - 子序列最大优雅度 (Maximum Elegance of a K-Length Subsequence) 困难

  提示

  反悔贪心利润替换与类别种类数权衡。

  • 优雅度 = 利润总和 \(+ distinct\_categories^2\)。
  • 先按利润降序排序，贪心选取前 \(k\) 个利润最大的项目，计算初始利润与种类数；
  • 用栈记录前 \(k\) 个项目中属于重复类别（即类别频次 \(\ge 2\)）的项目利润；
  • 遍历第 \(k+1\) 到 \(n\) 个项目：若当前项目属于全新类别，我们可以尝试用它替换掉前 \(k\) 个项目中重复类别的某个最小利润项（从栈顶弹出），种类数加 1，更新全局最大优雅度。
  • 时间复杂度 \(\mathcal{O}(N \log N)\)。

• LeetCode 1353 - 最多可以参加的会议数目 (Maximum Number of Events That Can Be Attended) 中等

  提示

  时间轴扫描线 + 小顶堆维护最早结束会议。

  • 每天只能参加一场会议，必须在 \([startDay, endDay]\) 范围内参加。
  • 贪心策略：在第 \(d\) 天，面对所有已经开始且尚未结束的会议，必须优先参加结束时间最早的会议（因为结束时间越早的会议越紧迫，后续越容易过期）！
  • 维护一个小顶堆存储当前所有可用会议的结束时间：
  • 将会议按开始时间升序排序；
  • 从第 1 天推进到最后一天：
    • 将所有今天开始的会议的结束时间加入小顶堆；
    • 剔除小顶堆中所有已经过期的会议（结束时间 \(< d\)）；
    • 若堆非空，贪心参加堆顶会议（pq.pop()），已参加数加 1；
  • 时间复杂度 \(\mathcal{O}((N + \max Day) \log N)\)。

• LeetCode 2434 - 使用机器人打印字典序最小的字符串 (Using a Robot to Print Lexicographically Smallest String) 中等

  提示

  后缀字符最小值预处理 + 栈模拟反悔贪心。

  • 目标：将字符串通过栈缓冲操作，输出字典序最小的字符串。
  • 核心贪心原则：在任何时刻，只要栈顶字符 \(\le\) 原字符串中剩余所有未入栈字符的最小值，就必须立即贪心弹出栈顶打印！因为留在栈里只会让它被后续字符压住，导致字典序变大。
  • 预处理后缀最小值数组 min_suf[i] 表示 \(s[i \dots n-1]\) 中的最小字符；
  • 遍历字符串 \(s[i]\)：
  • 将 \(s[i]\) 压入栈；
  • while 循环检查：若栈非空且栈顶字符 \(\le min\_suf[i + 1]\)（若 \(i+1 == n\) 则直接全部弹出），贪心弹出栈顶加入结果；
  • 时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(N)\)。