贪心算法

引言：从「走一步看一步」到「步步最优」

在算法世界里，有两类策略恰好处于光谱的两端。一类是「把所有可能都试一遍再回溯」的搜索派——DFS、回溯、动态规划都属于这一脉，它们宁可付出指数级代价也要保证不漏掉任何一种可能。另一类则是「看眼前、不回头」的贪心派——每一步都基于当前可观察的信息做出最优决策，做完就不再反悔。

贪心算法 (Greedy Algorithm) 听起来朴素得近乎天真：在每一步都做出当前看起来最好的选择，期望这一系列局部最优能累加成全局最优。然而这种「天真」背后隐藏着深刻的理论问题——为什么有时候它确实奏效，有时候又会给出离谱的答案？

考虑一个最朴素的场景：你要从 A 地去 B 地，途中有多条岔路。如果每到一个岔路口都选择「看起来离 B 更近的那条」，能不能保证最终走到 B 的总路程最短？答案是：不一定。因为眼前看似更近的路可能在下一个路口把你引向死胡同或绕远路。这正是贪心算法最容易被诟病的地方——局部最优未必导向全局最优。

但奇怪的是，对于相当多经典问题——找零（特定币制）、活动安排、区间调度、Huffman 编码、Dijkstra 最短路、最小生成树——贪心策略不仅给出正确答案，而且时间复杂度远低于动态规划。这背后一定有某种「结构上的保证」让贪心成立。理解这种保证、能判断它何时成立、能用严谨的方式证明它，就是本章要解决的核心问题。

学会贪心算法，本质上是学会三件事：

1. 识别：什么样的问题具备贪心可解的结构。
2. 构造：如何设计一个正确的贪心策略（关键是确定「按什么顺序、选什么」）。
3. 证明：如何用交换论证或归纳法说服自己和他人，这个策略确实能得到最优解。

本章会按这条主线展开。我们先建立直觉，再给出框架，然后逐个剖析经典例题，最后讨论贪心失效的边界与反例。

核心思想与正确性直觉

贪心的两个理论支柱

一个问题能用贪心求解，通常需要同时满足两个性质：

贪心选择性质 (Greedy Choice Property)：全局最优解可以通过一系列局部最优选择来达到。换句话说，做出一个贪心选择后，剩下的子问题仍然能被独立求解并最终拼出整体最优解——这个贪心选择不会「封死」通往最优的道路。

最优子结构 (Optimal Substructure)：问题的最优解包含子问题的最优解。这个性质其实动态规划也需要，所以它不是贪心独有的。真正区分贪心与 DP 的是「贪心选择性质」：DP 在每一步保留所有可能的子问题解，而贪心只保留一个——它敢这么做，是因为问题结构保证「其它分支注定不会更优」。

直觉：为什么排序几乎总是贪心的第一步

观察绝大多数贪心算法，会发现它们都遵循同一个模式：先排序，再按顺序做一次性决策。这不是巧合。

排序的本质是给所有候选元素赋予一个全局的「优先级」。一旦确定了优先级（比如按结束时间升序、按单位价值降序），贪心策略就退化为一个简单的扫描过程：遇到一个元素就决定「要」或「不要」，决策只依赖当前状态，不依赖未来。

例如活动选择问题，如果按结束时间排序，那么每选一个最早结束的活动，就给后续留出了最大的余地。这种「留余地」的直觉就是贪心成立的关键：当前选择虽然只是局部最优，但它对未来的约束最小，因此不会比任何其他选择更差。

贪心 vs DP：相同的支柱，不同的胆量

最优子结构是 DP 和贪心共用的，但 DP 假设「我不知道哪一步最优，所以全保留」，贪心则假设「我知道这一步最优是哪个，只保留它」。这种「知道」的底气来自贪心选择性质——它是一种更强的结构保证。

举个对比：

• 分数背包：物品可分割，按单位价值降序贪心即可。贪心成立，因为可以「填满」剩余容量。
• 0-1 背包：物品不可分割，贪心会失效（高价值物品可能太大塞不下），必须用 DP 枚举所有「选/不选」组合。

两者都有最优子结构，差别就在「贪心选择性质」是否成立。识别这一点，是从「会写 DP」到「会写贪心」的关键一跃。

贪心正确性证明

「这个贪心为什么对？」是面试和竞赛里最容易被追问的问题，也是初学者最容易卡壳的环节。掌握两种标准证明模板，能让你面对任何新问题都有章可循。

方法一：交换论证 (Exchange Argument)

交换论证的核心思路是反证加构造。假设贪心解 G 不是最优解，那么存在另一个最优解 O 与 G 不同。然后我们证明：可以把 O 中与 G 不同的部分「交换」成 G 的选择，且交换后解不变得更差。反复交换后，O 就变成了 G，而 O 是最优的，所以 G 也是最优的——矛盾。

具体步骤：

1. 假设 O 是一个与 G 不同的最优解。
2. 找到 O 与 G 第一个不同的决策点。
3. 把 O 在该点的决策替换为 G 的决策，证明替换后的 O’ 仍然合法且不比 O 差。
4. 因为 O’ ≤ O（更优或相等）且 O 是最优，所以 O’ 也是最优。
5. 重复直到 O 完全变成 G，故 G 是最优。

这种方法的关键在于第 3 步的「不变得更差」——它往往依赖问题本身的交换不变量。

方法二：数学归纳法

归纳法更适合「贪心保持领先 (Greedy Stays Ahead)」型问题。思路是证明：贪心在第 k 步做出的选择，在任何最优解中都能找到「等价或更好」的对应。

步骤：

1. 归纳基础：贪心第 1 步选择 g1，证明存在最优解以 g1 开头（或包含 g1 的等价物）。
2. 归纳假设：假设贪心前 k 步选择 g1…gk 能扩展为某个最优解。
3. 归纳步骤：证明前 k+1 步 g1…gk+1 也能扩展为最优解。

只要归纳成立，最终的贪心解就是最优的。

方法三：贪心保持领先 (Greedy Stays Ahead)

这是归纳法的一个具体化，常用于「最大化某个度量」的问题。证明贪心在每一步的累计度量都 ≥ 任何其他解的对应度量。最后一步贪心自然也是最大的。

下面我们会在活动选择问题里实操交换论证，在 Huffman 编码里看到归纳思想，让证明变得可触摸。

算法框架与模板

绝大多数贪心算法可以套用下面这个模板：

1. 把候选集合按某种「优先级」排序（或放入堆、队列）
2. 初始化解集 S = 空
3. while 候选集非空:
       取出优先级最高的元素 x
       if x 可以加入 S（不违反约束）:
           S = S ∪ {x}
           更新状态
4. 返回 S

注意三个关键点：

• 排序键的设计：这是贪心最核心的创造性环节。错误的排序键会让贪心彻底失效。
• 可行性检查：判断当前元素能否加入解集，往往涉及维护某些状态（如已用容量、当前结束时间）。
• 状态更新：加入元素后要及时更新状态，为下一步决策提供正确信息。

C++ 的通用骨架：

#include <vector>
#include <algorithm>

// 通用贪心骨架（伪代码风格）
template <typename T, typename Compare, typename Feasible, typename Update>
auto greedy(std::vector<T>& items, Compare cmp, Feasible ok, Update upd) {
    std::sort(items.begin(), items.end(), cmp);
    std::vector<T> solution;
    // state 是与具体问题相关的状态对象
    for (const auto& it : items) {
        if (ok(it /*, state */)) {
            solution.push_back(it);
            upd(it /*, state */);
        }
    }
    return solution;
}

实战中很少写出这种泛型模板，但它的精神值得记住：排序 → 扫描 → 一次性决策。

经典示例

下面我们逐一剖析经典贪心问题。每个示例都包含问题描述、思路分析、完整可编译代码、复杂度分析以及变种讨论。

示例 1：找零问题

问题描述：给定一组硬币面额 coins[] 和一个金额 amount，求用最少数量的硬币凑出该金额。若无法凑出返回 -1。

思路：在「标准币制」（如 1、5、10、25 美分，或人民币 1、5、10、20、50、100）下，每次选面额最大的硬币不会让结果更差。直觉是：大面额硬币「性价比」更高——用一枚就抵消很多小面额。

但要注意：贪心成立的条件是币制具有「拟素数性质」，即每个大面额都是小面额的整数倍或满足某种可整除关系。人民币和美分币制满足这一点，所以贪心有效；而一旦面额是任意的（如 [1, 3, 4] 凑 6），贪心就会失效。

#include <vector>
#include <algorithm>
#include <iostream>

// 标准币制下的贪心找零
// 假设 coins 已按面额降序排列，且币制满足贪心性质
int coinChangeGreedy(std::vector<int>& coins, int amount) {
    // 防御性排序：确保从大到小
    std::sort(coins.begin(), coins.end(), std::greater<int>());
    int count = 0;
    int i = 0;
    while (amount > 0 && i < (int)coins.size()) {
        if (coins[i] <= amount) {
            // 当前最大面额能用多少用多少
            int take = amount / coins[i];
            count += take;
            amount -= take * coins[i];
        }
        i++;
    }
    return amount == 0 ? count : -1;
}

int main() {
    std::vector<int> coins = {100, 50, 20, 10, 5, 1};  // 人民币币制
    int amount = 93;  // 50 + 20 + 20 + 1 + 1 + 1 = 6 枚
    std::cout << coinChangeGreedy(coins, amount) << "\n";  // 输出 6
    return 0;
}

复杂度分析：排序 O(n log n)，扫描 O(n)，总体 O(n log n)。空间 O(1)。

正确性证明（交换论证）：在标准币制下，每个大面额 c_{i+1} 都是 c_i 的整数倍。假设最优解 O 不使用尽可能多的大面额硬币，那么 O 中一定有若干枚 c_i 可以合并成一枚 c_{i+1}。把它们合并后硬币数减少——但 O 已经是最优，矛盾。故最优解必然「尽可能多用大面额」，即贪心解。

反例：任意币制下贪心失效

// 反例：coins = {1, 3, 4}, amount = 6
// 贪心选 4 + 1 + 1 = 3 枚
// 最优解 3 + 3 = 2 枚
// 此时应改用 DP

对于任意币制，必须使用动态规划：

#include <vector>
#include <algorithm>

// 任意币制下的找零（DP 解法）
int coinChangeDP(const std::vector<int>& coins, int amount) {
    const int INF = amount + 1;
    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int c : coins) {
            if (c <= i && dp[i - c] + 1 < dp[i]) {
                dp[i] = dp[i - c] + 1;
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

这个对比极好地说明了贪心与 DP 的边界：相同的「最优子结构」，但贪心选择性质是否成立决定了能不能用贪心。

示例 2：跳跃游戏

问题描述（LeetCode 55）：给定非负整数数组 nums，nums[i] 表示从位置 i 最多可以跳多远。初始在位置 0，判断能否到达最后一个位置。

思路：维护一个「当前能到达的最远位置」maxReach。扫描每个位置 i，如果 i 在 maxReach 范围内，就更新 maxReach = max(maxReach, i + nums[i])。若 maxReach 已覆盖末尾，返回 true；若扫描中 i 超过 maxReach，说明被卡住，返回 false。

贪心的关键在于：我们不需要决定「跳到哪个位置」，只需关心「能跳到的最远边界」。每一步把当前能延伸的边界尽量往外推，这种「维护最大可达」的策略天然正确。

#include <vector>
#include <algorithm>
#include <iostream>

// 跳跃游戏：判断能否到达末尾
bool canJump(std::vector<int>& nums) {
    int maxReach = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        // 如果当前位置已经超过能到达的最远位置，则被卡住
        if (i > maxReach) return false;
        // 贪心：尽量扩展能到达的最远边界
        maxReach = std::max(maxReach, i + nums[i]);
        // 提前剪枝：已经能覆盖末尾
        if (maxReach >= n - 1) return true;
    }
    return true;
}

int main() {
    std::vector<int> nums1 = {2, 3, 1, 1, 4};  // 可达
    std::vector<int> nums2 = {3, 2, 1, 0, 4};  // 不可达
    std::cout << std::boolalpha
              << canJump(nums1) << "\n"  // true
              << canJump(nums2) << "\n"; // false
    return 0;
}

复杂度分析：O(n) 时间，O(1) 空间。比 BFS 或 DP 都更优。

正确性证明（贪心保持领先）：设 maxReach_k 为扫描前 k+1 个位置后能到达的最远位置。归纳证明 maxReach_k 是考虑前 k+1 个位置时的真正最大可达。任何能到达末尾的策略，其每一步都不会越过当前的 maxReach，故贪心判断等价于「存在一条路径」。

变种：跳跃游戏 II（最少跳跃次数）

#include <vector>
#include <algorithm>

// 跳跃游戏 II：最少跳跃次数到达末尾
int jump(std::vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;
    int jumps = 0;       // 已跳跃次数
    int curEnd = 0;      // 当前一跳能到达的边界
    int farthest = 0;    // 下一跳能到达的最远位置
    for (int i = 0; i < n - 1; ++i) {
        farthest = std::max(farthest, i + nums[i]);
        // 到达当前一跳的边界，必须再跳一次
        if (i == curEnd) {
            jumps++;
            curEnd = farthest;
            if (curEnd >= n - 1) break;
        }
    }
    return jumps;
}

这里的贪心策略是「在当前一跳的覆盖范围内，找到下一跳能到达的最远位置」。这是一种「分层 BFS」式的贪心——把每一跳的可达范围当作一层，逐层扩展。

示例 3：活动选择问题

问题描述：有 n 个活动，每个活动有开始时间 start 和结束时间 end，同一时刻只能进行一个活动。求能参加的最多活动数。

这是经典的区间调度问题，是贪心算法的「教科书级」案例。原文给出的代码如下，我们先保留它，再做深入分析。

#include <vector>
#include <algorithm>

struct Activity {
    int start, end;
};

// 按结束时间排序
int maxActivities(std::vector<Activity>& acts) {
    std::sort(acts.begin(), acts.end(), 
        [](const Activity& a, const Activity& b) {
            return a.end < b.end;
        });
    
    int count = 1;
    int last_end = acts[0].end;
    
    for (size_t i = 1; i < acts.size(); i++) {
        if (acts[i].start >= last_end) {
            count++;
            last_end = acts[i].end;
        }
    }
    return count;
}

为什么按结束时间排序？ 这是本问题的灵魂。考虑三种可能的排序键：

• 按 start 升序：最早开始的活动可能结束得很晚，把整个时间段占住，反而排除了很多短活动。
• 按 length 升序：最短的活动可能位置很尴尬，不一定能容纳更多。
• 按 end 升序：正确。最早结束的活动为后续留出了最大的剩余时间窗口。

正确性证明（交换论证）：

设贪心解 G = {g1, g2, …, gk}（按结束时间排序），最优解 O = {o1, o2, …, om}（也按结束时间排序）。已知 k ≤ m（贪心不会超过最优）。

我们要证 m ≤ k。考虑 o1 与 g1：

• 由于 g1 是所有活动中结束最早的，故 g1.end ≤ o1.end。
• 把 O 中的 o1 替换为 g1：因为 g1.end ≤ o1.end，g1 不会与 o2 冲突（o2.start ≥ o1.end ≥ g1.end），所以替换后的 O’ = {g1, o2, …, om} 仍是合法解，且活动数不变。
• 重复此过程，可将 O 逐个替换为 G 的前 k 个元素。若 m > k，则在第 k 次替换后 O 仍剩至少一个活动 ok+1，但 G 已选完，意味着 ok+1.start ≥ gk.end。然而贪心在第 k 步后还会继续扫描——既然 ok+1 合法，贪心应该会选它，矛盾。故 m = k。

这个证明完美展示了交换论证的力量：把最优解「改造」成贪心解，且不损失最优性。

复杂度分析：排序 O(n log n)，扫描 O(n)，总体 O(n log n)。空间 O(1)（原地排序）或 O(n)（保留原序）。

变种：

1. 加权活动选择：每个活动有权值，求最大权值和。此时贪心失效，需用 DP（按结束时间排序后 dp[i] = max(dp[i-1], w[i] + dp[p[i]])，其中 p[i] 是不与 i 冲突的最后一个活动）。
2. 区间选点问题：选最少的点，使每个区间至少含一个点。按结束时间排序，每次选结束点即可。
3. 最大不相交区间数：等价于本问题。

示例 4：区间调度问题（最少会议室）

问题描述（LeetCode 253）：给定一组会议时间区间 [start, end)，求需要的最少会议室数（同一会议室同一时刻只能开一个会）。

这是「活动选择」的对偶问题：前者是「单资源下选最多活动」，后者是「固定活动下分配最少资源」。原文代码如下：

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

int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    
    std::sort(intervals.begin(), intervals.end());
    
    // 最小堆，存储每个会议室的结束时间
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(intervals[0][1]);
    
    for (size_t i = 1; i < intervals.size(); i++) {
        // 最早结束的会议已经结束
        if (intervals[i][0] >= pq.top()) {
            pq.pop();
        }
        pq.push(intervals[i][1]);
    }
    return pq.size();
}

思路分析：按开始时间排序后逐个处理会议。维护一个最小堆，堆顶是「最早结束的会议室」。

• 如果当前会议开始时已有会议室空闲（intervals[i][0] >= pq.top()），就复用该会议室（pop 旧的，push 新的结束时间）。
• 否则必须新开一间会议室（直接 push）。

最终堆的大小就是所需会议室数。贪心直觉：总是优先复用最早结束的会议室，因为它的「可用窗口」最早开启，最有可能被新会议复用；让结束晚的会议室继续被占用，反而限制了灵活性。

为什么这样是对的？ 思考「在任意时刻，正在进行的会议数的最大值」就是所需会议室数。这个最大值是下界（至少要这么多间）。我们的贪心策略恰恰保证：会议室数等于任意时刻并发会议数的峰值。可以用「时间扫描线」理解——把所有 start 和 end 事件按时间排序，遇到 start 计数 +1，遇到 end 计数 -1，过程中的最大计数即为答案。堆方法与之等价但更省事件数。

正确性证明：用「贪心保持领先」证明。设贪心在第 i 步后用 R_i 间会议室，而最优解用 O_i 间。可证 R_i ≤ O_i（归纳：每一步贪心都尽量复用，所以不会比最优解多用）。又因为最优解是下界，R_i = O_i。

复杂度分析：排序 O(n log n)，堆操作每次 O(log n)，共 n 次，总体 O(n log n)。空间 O(n)。

变种：扫描线写法

#include <vector>
#include <algorithm>

// 扫描线解法：把 start/end 当作事件
int minMeetingRoomsSweep(std::vector<std::vector<int>>& intervals) {
    std::vector<std::pair<int, int>> events;
    for (auto& it : intervals) {
        events.push_back({it[0], +1});  // 开始
        events.push_back({it[1], -1});  // 结束
    }
    // 关键：同一时刻 end 优先于 start（结束先于开始才不冲突）
    std::sort(events.begin(), events.end(), [](auto& a, auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;  // -1 在 +1 之前
    });
    int cur = 0, ans = 0;
    for (auto& [t, d] : events) {
        cur += d;
        ans = std::max(ans, cur);
    }
    return ans;
}

扫描线写法更直观，且避免了堆操作。注意同一时刻 end 必须排在 start 之前——若 start 先到，会多算一间会议室。

示例 5：任务调度器

问题描述（LeetCode 621）：给定一个字符数组 tasks 表示 CPU 任务，相同任务之间需要间隔 n 个冷却周期。求完成所有任务的最少时间。

思路：贪心策略是「按任务剩余次数从多到少调度」。最关键洞察是：

• 出现次数最多的任务决定了「骨架」。设最频繁任务出现 maxFreq 次，则至少需要 (maxFreq - 1) * (n + 1) + maxCount 时间（其中 maxCount 是出现 maxFreq 次的任务种类数）。
• 这个值是理论下界。如果其它任务能填满冷却空隙，答案就是任务总数 tasks.size()；否则取上述下界。

#include <vector>
#include <algorithm>
#include <array>

// 任务调度器：相同任务间隔至少 n 个周期
int leastInterval(std::vector<char>& tasks, int n) {
    std::array<int, 26> freq{};
    for (char t : tasks) freq[t - 'A']++;
    
    int maxFreq = *std::max_element(freq.begin(), freq.end());
    
    // 出现 maxFreq 次的任务种类数
    int maxCount = 0;
    for (int f : freq) if (f == maxFreq) maxCount++;
    
    // 理论下界：(maxFreq - 1) 段冷却 + 最后一段
    int lower = (maxFreq - 1) * (n + 1) + maxCount;
    
    // 答案取下界与任务总数的较大值
    return std::max(lower, (int)tasks.size());
}

贪心直觉：最频繁的任务是最「受限」的——它需要的冷却间隙最多。如果我们先排好最频繁任务的骨架，剩余任务自然能填入空隙。当任务足够多时，空隙被填满，总时间就是任务总数；当任务不够时，必须等待冷却，时间是下界。

复杂度分析：统计频次 O(n)，计算 O(1)，总体 O(n)。空间 O(1)（26 个字母）。

模拟写法（用堆）：如果问题变种为「求具体调度序列」或冷却规则更复杂，需要用最大堆模拟每一轮：

#include <vector>
#include <queue>
#include <unordered_map>

// 模拟写法：每轮选剩余次数最多且不在冷却中的任务
int leastIntervalSim(std::vector<char>& tasks, int n) {
    std::unordered_map<char, int> freq;
    for (char t : tasks) freq[t]++;
    
    // 最大堆：按剩余次数排序
    auto cmp = [](std::pair<char, int>& a, std::pair<char, int>& b) {
        return a.second < b.second;
    };
    std::priority_queue<std::pair<char, int>, 
                        std::vector<std::pair<char, int>>, 
                        decltype(cmp)> pq(cmp);
    for (auto& [t, c] : freq) pq.push({t, c});
    
    int time = 0;
    while (!pq.empty()) {
        std::vector<std::pair<char, int>> tmp;
        int cycle = n + 1;  // 一轮冷却周期
        int done = 0;
        for (int i = 0; i < cycle && !pq.empty(); ++i) {
            auto [t, c] = pq.top(); pq.pop();
            if (c > 1) tmp.push_back({t, c - 1});
            done++;
        }
        for (auto& p : tmp) pq.push(p);
        // 如果堆空了，本轮实际只用了 done 个时间；否则用满 cycle
        time += pq.empty() ? done : cycle;
    }
    return time;
}

模拟写法更通用，但常数大。公式法是数学化简后的最优解。

示例 6：Huffman 编码

问题描述：给定一组字符及其出现频率，为每个字符构造一个二进制前缀编码，使编码后总长度（按频率加权）最短。

思路：Huffman 算法是贪心的经典代表。每次从频率集合中选出两个最小的，合并成一个新节点（频率为两者之和），重复直到只剩一个根节点。最终每个字符的编码是从根到叶路径上的 0/1 序列。

贪心直觉：频率低的字符编码长一些无妨（它们出现少），频率高的字符编码短（出现多，省下的位数多）。每次合并两个最小的，等价于「给它们各自加一位编码」——这一位编码分摊在两个最低频字符上，总成本最小。

#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <iostream>

struct HuffNode {
    char ch;        // 叶子节点存字符，内部节点用 '\0'
    int freq;
    HuffNode* left;
    HuffNode* right;
    HuffNode(char c, int f, HuffNode* l = nullptr, HuffNode* r = nullptr)
        : ch(c), freq(f), left(l), right(r) {}
};

// 比较器：频率小的优先
struct cmp {
    bool operator()(HuffNode* a, HuffNode* b) {
        return a->freq > b->freq;  // 最小堆
    }
};

// 构建 Huffman 树
HuffNode* buildHuffmanTree(const std::vector<char>& chars,
                           const std::vector<int>& freqs) {
    std::priority_queue<HuffNode*, std::vector<HuffNode*>, cmp> pq;
    for (size_t i = 0; i < chars.size(); ++i) {
        pq.push(new HuffNode(chars[i], freqs[i]));
    }
    while (pq.size() > 1) {
        HuffNode* l = pq.top(); pq.pop();
        HuffNode* r = pq.top(); pq.pop();
        // 合并：内部节点频率为子树频率之和
        pq.push(new HuffNode('\0', l->freq + r->freq, l, r));
    }
    return pq.top();
}

// 递归生成编码表
void genCodes(HuffNode* root, std::string cur,
              std::unordered_map<char, std::string>& table) {
    if (!root) return;
    if (root->ch != '\0') {  // 叶子
        table[root->ch] = cur.empty() ? "0" : cur;
        return;
    }
    genCodes(root->left,  cur + "0", table);
    genCodes(root->right, cur + "1", table);
}

int main() {
    std::vector<char> chars = {'a', 'b', 'c', 'd', 'e', 'f'};
    std::vector<int>  freqs = { 5,   9,   12,  13,  16,  45 };
    HuffNode* root = buildHuffmanTree(chars, freqs);
    std::unordered_map<char, std::string> table;
    genCodes(root, "", table);
    for (auto& [c, code] : table) {
        std::cout << c << ": " << code << "\n";
    }
    return 0;
}

复杂度分析：建堆 O(n)，每次合并 O(log n)，共 n-1 次合并，总体 O(n log n)。空间 O(n)。

正确性证明（交换论证 + 归纳）：

Huffman 编码的最优性证明是贪心理论中的经典。核心思路：

1. 引理 1：存在一棵最优前缀码树，其中频率最低的两个字符是兄弟叶子，且位于最深处。证明用交换论证：若最优树 T 中频率最低的字符 x 不在最深，则把它与最深的叶子 y 交换，由于 freq[x] ≤ freq[y]，交换后总代价不增。
2. 引理 2：把频率最低的两个字符 x、y 合并成一个虚拟字符 z（频率 freq[x] + freq[y]），对剩余字符集求最优树 T’。把 T’ 中的 z 拆回 x、y 子树，得到的树 T 是原问题的最优树。这建立了「最优子结构」。
3. 归纳：Huffman 算法每步都执行引理 1、2 描述的操作，故最终得到的树是最优的。

这个证明同时展示了交换论证（引理 1）和最优子结构（引理 2）的应用，是贪心理论的范本。

前缀码性质：Huffman 编码是前缀码（没有任何编码是另一个的前缀），因此解码时不会产生歧义。这一性质来自二叉树的叶子结构——所有字符都在叶子，路径天然不互相包含。

示例 7：Dijkstra 算法视作贪心

问题描述：给定非负权图和源点 s，求 s 到所有其它顶点的最短路径。

思路：Dijkstra 算法本质上是贪心——每次从「未确定最短路径」的顶点中选距离源点最近的，将其「确定」下来，然后用它更新邻居。这个「选最近的」就是贪心选择。

贪心成立的关键：图的非负权性质。因为所有边权非负，一旦确定某顶点 u 的最短距离 d[u]，任何「绕远路」到达 u 的路径都不可能更短。这正是贪心选择性质的来源。

#include <vector>
#include <queue>
#include <climits>
#include <iostream>

struct Edge {
    int to, weight;
};

// Dijkstra：单源最短路（非负权图）
std::vector<int> dijkstra(int n, int src,
                          const std::vector<std::vector<Edge>>& graph) {
    std::vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    // 最小堆：(距离, 顶点)
    std::priority_queue<std::pair<int,int>,
                        std::vector<std::pair<int,int>>,
                        std::greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        // 贪心选择：当前最近的未确定顶点
        if (d > dist[u]) continue;  // 过期数据，跳过
        for (const auto& e : graph[u]) {
            int nd = d + e.weight;
            if (nd < dist[e.to]) {  // 松弛操作
                dist[e.to] = nd;
                pq.push({nd, e.to});
            }
        }
    }
    return dist;
}

int main() {
    int n = 5;
    std::vector<std::vector<Edge>> g(n);
    g[0].push_back({1, 10});
    g[0].push_back({4, 5});
    g[1].push_back({2, 1});
    g[1].push_back({4, 2});
    g[2].push_back({3, 4});
    g[3].push_back({2, 6});
    g[3].push_back({0, 7});
    g[4].push_back({1, 3});
    g[4].push_back({2, 9});
    g[4].push_back({3, 2});
    
    auto dist = dijkstra(n, 0, g);
    for (int i = 0; i < n; ++i) {
        std::cout << "0 -> " << i << " = " << dist[i] << "\n";
    }
    return 0;
}

复杂度分析：使用最小堆，每次取最小 O(log V)，每条边松弛一次 O(E log V)，总体 O((V+E) log V)。

为什么这是贪心：

• 每一步从未确定顶点中选距离最小的——这是贪心选择。
• 一旦确定，不再修改——这是贪心的「不反悔」特性。
• 贪心选择性质由非负权保证：若存在更短路径经过未确定顶点，那条路径的边权之和必为正，不可能让确定值变小。

为什么负权图上 Dijkstra 失效：一旦有负权，贪心选择性质就被破坏——一条「看起来更远」的路径可能通过负边变得更短。Bellman-Ford 通过反复松弛所有边（DP 思想）来处理负权，是贪心失效时退回 DP 的典型例子。

正确性证明（贪心保持领先）：归纳证明。设 d[u] 为 u 被确定时的距离值。归纳基础：源点 s 的 d[s] = 0 正确。归纳步骤：设所有已确定顶点的 d 值都是真正的最短距离，现在确定 u（堆顶）。假设存在更短路径 P 到 u，P 必经过某个未确定顶点 v。但 d[v] ≥ d[u]（因为 u 是堆顶），且从 v 到 u 的路径长度非负，故 P 的长度 ≥ d[v] ≥ d[u]，矛盾。所以 d[u] 是真正的最短距离。

贪心失效的反例

学会识别贪心失效的场景，与学会使用贪心同样重要。下面几个反例展示了贪心选择性质不成立时会发生什么。

反例 1：0-1 背包

问题描述：n 个物品，每个有重量 w_i 和价值 v_i，背包容量 W。每个物品要么全选要么不选，求最大价值。

贪心策略（按单位价值降序）：

#include <vector>
#include <algorithm>

struct Item { int w, v; };

double fractionalGreedy(std::vector<Item>& items, int W) {
    // 按单位价值降序
    std::sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return (double)a.v / a.w > (double)b.v / b.w;
    });
    double total = 0;
    int cap = W;
    for (auto& it : items) {
        if (it.w <= cap) {
            cap -= it.w;
            total += it.v;
        }
        // 0-1 背包：物品不可分割，跳过；分数背包：可部分装入
    }
    return total;
}

反例数据：物品 {(w=10, v=60), (w=20, v=100), (w=30, v=120)}，容量 50。

• 贪心按单位价值排序：60/10=6, 100/20=5, 120/30=4。先选 (10,60)，剩容量 40；再选 (20,100)，剩容量 20；(30,120) 装不下。总价值 160。
• 最优解：选 (20,100) + (30,120) = 220。

贪心失效，因为「单位价值最高」的物品「太大」，挡住了更优组合。0-1 背包必须用 DP：

#include <vector>
#include <algorithm>

// 0-1 背包 DP 解法
int knapsack01(std::vector<Item>& items, int W) {
    int n = items.size();
    std::vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i) {
        // 逆序更新，避免重复使用
        for (int j = W; j >= items[i].w; --j) {
            dp[j] = std::max(dp[j], dp[j - items[i].w] + items[i].v);
        }
    }
    return dp[W];
}

对比：分数背包：物品可分割时，上述贪心立刻正确。因为「装不下就装一部分」消除了「物品大小」的约束，单位价值排序直接给出最优。

这一对反例极好地诠释了「贪心选择性质」的微妙：能否分割决定了贪心是否成立。

反例 2：旅行商问题 (TSP)

问题描述：访问所有城市各一次后回到起点，求最短路径。

最近邻贪心：每步选最近的未访问城市。这个策略在大规模实例上效果很差——它在前期可能省距离，但后期被迫走长边回起点，总长可能远超最优。TSP 是 NP-hard，不存在多项式贪心解。

反例 3：最小 coloring

问题描述：给图顶点着色，相邻顶点不同色，求最少颜色数。

贪心策略：按某种顺序遍历顶点，每个顶点用「最小可用颜色」。这个策略在一般情况下不是最优——顺序的选择极大影响结果，且最优着色数（色数）的计算是 NP-hard。

反例 4：找零（再回顾）

前面已经提到：币制 [1, 3, 4] 凑 6，贪心给 4+1+1=3 枚，最优是 3+3=2 枚。币制缺乏「拟素数性质」时贪心失效，必须用 DP。

反例总结

观察这些反例，会发现一个共性：贪心失效往往因为「当前最优选择会限制未来选择」。0-1 背包里大物品挤占容量；TSP 里前期省距离导致后期被迫绕远；找零里大面额错失组合机会。当问题的最优解需要「全局权衡」而非「局部累加」时，贪心就会失效，DP 或搜索是更稳妥的选择。

贪心与 DP 的边界

贪心和 DP 共享「最优子结构」，但用截然不同的方式利用它。理解两者的边界，是算法设计的核心能力。

关键差异

维度	贪心	动态规划
决策方式	每步只保留一个最优选择	保留所有子问题解
时间复杂度	通常 O(n log n)	通常 O(n^2) 或 O(nW)
适用条件	贪心选择性质 + 最优子结构	最优子结构 + 子问题重叠
正确性	需证明贪心选择性质	由最优子结构天然保证
反悔	不反悔	通过状态转移隐式枚举

判断流程

遇到一个最优化问题，建议按以下顺序判断：

1. 是否有最优子结构？ 若没有，贪心和 DP 都不适用，需用搜索或回溯。
2. 是否有贪心选择性质？ 即「做出一个局部最优选择后，剩下的子问题能否独立最优地求解」。若能，尝试贪心，并用交换论证证明。
3. 若贪心选择性质不成立或难以判断，转用 DP。DP 通过枚举所有「选/不选」组合天然避免贪心陷阱。
4. 若 DP 状态空间过大（如背包容量极大），考虑贪心近似或其它启发式。

同一问题的贪心/DP 转换

某些问题在不同约束下贪心与 DP 互换：

• 背包：分数 → 贪心；0-1 → DP。
• 最短路：非负权 → Dijkstra（贪心）；负权 → Bellman-Ford（DP）。
• 活动选择：等权 → 贪心；加权 → DP。
• 区间调度：最少会议室 → 贪心（堆或扫描线）；加权最大独立集 → DP。

这种「同源异构」非常常见，掌握它需要的是对问题结构的敏感度——而敏感度来自大量练习和对正确性证明的理解。

实战场景

竞赛中的应用

贪心在算法竞赛中是「性价比最高」的算法之一——代码短、复杂度低、容易拿分。常见题型：

1. 排序 + 贪心：活动选择、区间合并、分发糖果、田忌赛马。
2. 堆 + 贪心：合并果子、Huffman、会议室调度、数据流中位数。
3. 扫描线：区间覆盖、点覆盖、矩形面积并。
4. 图论贪心：最小生成树（Kruskal/Prim）、Dijkstra、拓扑排序的字典序最小。
5. 数学贪心：删数问题、数位构造、进制转换。

竞赛中识别贪心题型的方法：

• 问题问「最大/最小/最多/最少」且数据范围较大（排除指数级搜索）。
• 直觉上有「优先处理某种特殊元素」的策略。
• 存在明确的排序键，且决策可一次性完成。

工程中的应用

工程实践中贪心算法的应用场景：

1. 任务调度：操作系统进程调度（最短作业优先 SJF）、网络包调度。
2. 资源分配：内存分配（首次适应、最佳适应）、磁盘空间管理。
3. 数据压缩：Huffman 编码（gzip、JPEG、MP3 等格式中都用到）。
4. 网络路由：链路状态路由协议（OSPF）基于 Dijkstra。
5. 缓存替换：LRU 是贪心（淘汰最久未用），但最优替换（Belady）需要未来信息，是贪心的上界参考。
6. 聚类：单链接层次聚类本质是贪心（最小生成树的衍生）。
7. 近似算法：许多 NP-hard 问题（集合覆盖、TSP）用贪心做近似，且有理论保证（如集合覆盖贪心是 ln n 近似）。

一个工程实例：Huffman 在 gzip 中

gzip 使用 DEFLATE 算法，其中包含 Huffman 编码。文件被分成块，每块统计字节频率后构造 Huffman 树，再把字节流编码为 Huffman 码流。这是贪心算法在工程中的典型应用——Huffman 编码的最优性保证让压缩比有理论上界。

一个工程实例：Dijkstra 在 OSPF 中

OSPF（开放式最短路径优先）是互联网内部网关协议，每个路由器维护全网链路状态图，用 Dijkstra 计算到所有目标的最短路径树。链路权值非负（带宽/延迟的倒数），贪心成立，使得 OSPF 能高效收敛。

常见陷阱与边界条件

陷阱 1：排序键设计错误

最常见的陷阱是排序键选错。例如活动选择若按开始时间排序，会得到错误答案。设计贪心时，务必问自己：「为什么这个排序键能让贪心成立？」若答不上来，多半排序键错了。

自检方法：构造小规模反例手工验证。把贪心解和暴力解在小数据上对比，能快速发现排序键问题。

陷阱 2：忽略稳定性与同序处理

当多个元素排序键相同时，处理顺序可能影响结果。例如扫描线中，同一时刻 start 和 end 的先后顺序必须仔细规定（end 先于 start 才不会多算会议室）。要明确同序元素的处理规则，避免「未定义行为」。

陷阱 3：忘记检查可行性

贪心骨架中「可行性检查」不可省略。例如背包贪心中，必须检查物品能否装入；活动选择中，必须检查 start >= last_end。漏掉检查会得到非法解。

陷阱 4：混淆贪心与 DP

初学者容易把本应 DP 的问题强行贪心。如 0-1 背包、加权活动选择。判断原则：若不同选择会导向「不同且不可比较」的子问题（如选了 A 就不能选 B），多半是 DP 题。

陷阱 5：忽视边界数据

• 空输入：intervals.empty() 时会议室数为 0，不能访问 intervals[0]。
• 单元素：活动只有 1 个时直接返回 1。
• 全相同：所有区间相同时会议室数为区间数。
• 极大值：硬币面额极大时 amount + 1 不能溢出。

陷阱 6：贪心「看起来对」实则错

某些贪心策略在小数据上正确，大数据上错误。如「按价值降序选物品」在 0-1 背包上的反例需要特定数据才暴露。要养成「找反例」的习惯，而非「举例验证」——举例只能证伪，不能证明。

陷阱 7：堆的过期数据

Dijkstra 用 if (d > dist[u]) continue; 跳过过期堆项，是常见优化。若不加这一行，时间复杂度会退化。最小堆中可能存在同一顶点的多个旧距离值，必须显式跳过。

陷阱 8：浮点精度

涉及单位价值排序（分数背包）时，浮点比较可能出错。建议用交叉乘法 a.v * b.w > b.v * a.w 代替 a.v/a.w > b.v/b.w，避免精度问题。

小结

贪心算法是算法设计中最考验「直觉 + 证明」双重能力的范式。它的代码往往极简，但正确性的判断和证明却需要扎实的理论功底。回顾本章核心要点：

1. 核心思想：每步做局部最优选择，期望全局最优。成立前提是「贪心选择性质」与「最优子结构」。
2. 判定关键：贪心选择性质——做出局部最优后，子问题仍能独立最优求解。
3. 证明方法：交换论证（把最优解改造为贪心解）和数学归纳（贪心保持领先）是两把标准武器。
4. 算法模板：排序 → 扫描 → 一次性决策。排序键的设计是核心创造性环节。
5. 经典问题：活动选择（按结束时间）、区间调度（堆或扫描线）、找零（标准币制）、跳跃游戏（维护最远边界）、任务调度（频次公式）、Huffman 编码（最小堆合并）、Dijkstra（非负权最短路）。
6. 失效边界：0-1 背包、TSP、负权最短路等问题贪心失效，需转 DP 或搜索。共性是「当前最优限制未来选择」。
7. 与 DP 的关系：共享最优子结构，差别在贪心选择性质是否成立。同一问题在不同约束下可能在贪心与 DP 间切换。

掌握贪心算法的最佳路径是「写 + 证 + 反例」三位一体：写代码加深直觉，证正确性锤炼思维，找反例拓展边界。当你能对任意贪心策略快速给出证明或反例时，就真正理解了贪心算法的精髓。

最后送一句话给读者：贪心算法的迷人之处在于，它用最朴素的眼光看世界，却在结构保证下达到了最优。理解这种「朴素中的深刻」，是算法思维成熟的重要标志。