Algorithm · Greedy
每步只留一个选择的勇气：贪心选择性质 · 交换论证 · 区间调度与跳跃游戏 —— 以及什么时候贪心会骗你
局部最优叠加成全局最优——前提是能证明，而不是祈祷
区间调度、跳跃游戏、分发问题——"排序 + 一次扫描"的套路家族
硬币反例 [1,3,4] 找 6：贪心 3 枚 vs 最优 2 枚——证明失败立刻回退 DP
Why Greedy
| 选会议的准则 | 直觉理由 | 结果 |
|---|---|---|
| 先到先得（按开始时间） | 时间最早的最优先 | ✗ 一个超长会议能吞掉一整天 |
| 每次挑最短的 | 短的占时间少 | ✗ 短会可能正好卡在两个长会中间 |
| 每次挑结束最早的 | 结束越早，留给后面的时间越多 | ✓ 一定是最多的 |
三个会议申请：[1,4]、[2,3]、[3,5]，你只有一间会议室。
按"开始最早"选 → 先拿 [1,4]，剩下 [2,3] 和 [3,5] 都冲突 → 只能开 1 个。
按"结束最早"选 → 先拿 [2,3]，再拿 [3,5] → 能开 2 个。
第一步的一个选择，直接决定了全局结果——这就是贪心的全部重量。
凭一个叫交换论证的东西：任取一个最优解，把它的第一个会议换成"结束最早的那个"，因为换上去的结束更早，绝不会和后面的会议产生新的冲突——所以最优解可以被"洗"成贪心解，且不变差。这三句话就是本 deck 的核心方法。
当"当前最好的选择会锁死未来更好的组合"时。经典反例——面值 [1,3,4] 找 6：贪心拿最大是 4+1+1 = 3 枚，最优是 3+3 = 2 枚。找不到反例 + 能交换论证，才敢交卷。
先立两个前提（什么时候配用贪心）→ 交换论证这套证明方法 → 区间调度 / 跳跃游戏 / 分发股票三大主场 -> 最后专门讲贪心失效与如何回退 DP。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 贪心 greedy | 每步选当前看起来最好的那个，并且永不反悔——不做试探、不回溯 |
| 局部最优 / 全局最优 | 局部最优 = 这一步的最佳选择；全局最优 = 整件事的最佳方案。贪心赌的就是"局部堆出全局" |
| 贪心选择性质 | 存在一个"当前最优选择"，它一定出现在某个全局最优解里——这是可以用数学证明的结构性质，不是"感觉上对" |
| 最优子结构 | 做出贪心选择后，剩下那个子问题的最优解拼上这个选择 = 原问题最优解（与 DP 共享这条） |
| 交换论证 | 贪心正确性的标准证明手法：把任意最优解里的某个选择逐步换成贪心选择，且论证每一步都不变差 |
| 排序准则 | 决定"每一步选谁"的那个排序键（右端点？左端点？权值？）。换一个排序准则 = 换一个贪心策略 |
| 反例 counterexample | 一个能让贪心给出非最优解的具体输入。构造反例是证伪的廉价武器——比正面证明容易得多 |
| 双向扫描 | 同时存在"比左邻大"和"比右邻大"两个方向约束时，各扫一遍再取 max（分发糖果） |
| 分层贪心 | 把"第 k 步能到达的范围"看成一个层，层内取最远（跳跃游戏 45，等价于隐式 BFS） |
| 单调结构 | 像"可达区间一定是连续前缀"这类单调性。发现单调结构，是把 O(n²) 的 DP 升级成 O(n) 贪心的信号 |
先读这几篇再回来。本 deck 默认你已经能读懂排序与循环：
动态规划 → 贪心证不出来时的退路
排序算法 → 贪心的第一步几乎总是排序
图算法 → Kruskal 与 Dijkstra 都是可证明的贪心
复杂度分析 → O(n log n) 从哪来
把贪心记成三个必须回答的问题：① 按什么排序？② 每步选什么？③ 为什么把这个选择换进任意最优解里，结果不会变差？前两问给你三行代码，第三问决定这段代码能不能交——面试里主动讲出第 ③ 问，才是这道题的完整答案。
正面证明一个贪心是对的往往很难，但推翻它只要一个具体输入。所以标准动作是：先花 30 秒试图构造反例（小 n 手推），构造不出来再去找交换论证。证伪比证明便宜，先做便宜的那件事。
Greedy Choice Property
上一页说"三条准则只有一条是对的"——那"结束最早"这条凭什么就是对的？答案在下面两个前提里：贪心不是想用就能用。
每一步做出当前看起来最优的选择，并且永不反悔。DP 保留所有选择让转移裁决；贪心在决策时刻就砍掉其余分支——所以快，所以要命。
存在一个"当前最优选择"，它出现在某个全局最优解里——砍掉它不丢最优性。这是可以用数学证明的结构性质，不是"感觉上对"。
做出贪心选择后，剩余子问题的最优解 + 贪心选择 = 原问题最优解（与 DP 共享这条性质）。
解最值题的顺序：先试贪心（O(n)）→ 证不出 → 降级 DP（O(n²)/O(n log n)）。贪心是 DP 的"剪枝极限"——每步只留一个分支的 DP。
| 对比维度 | 贪心 | DP |
|---|---|---|
| 每步选择数 | 1 个（砍掉其余） | 保留全部 |
| 正确性来源 | 证明（交换论证等） | 穷举所有转移 |
| 复杂度 | 通常 O(n log n)（排序） | 状态数 × 转移数 |
| 反悔能力 | 无 | 隐式全保留 |
| 适用面 | 窄（有选择性质） | 宽 |
Exchange Argument
① 设贪心选了结束最早的区间 g，任取最优解 OPT 的第一个区间 o；② 交换：把 OPT 里的 o 换成 g——g 结束更早，不会与 OPT 后续任何区间冲突；③ 得到同样规模的新最优解，且它包含 g → 归纳到底，贪心解 = 最优解。
"任意最优解 → 有限次交换 → 贪心解，且每次交换不变差"——最优解可以被"洗"成贪心解。
怀疑贪心错时，构造最小反例即可证伪：硬币 [1,3,4] 找 6。反例的存在性证明（"存在输入使贪心非最优"）比正面证明容易得多——证伪是廉价武器。
区间调度按右端点排序对、按左端点排序错（[1,100],[2,3] 会先吃掉大区间）。换一个排序准则 = 换一个贪心策略——找对准则本身就是证明的一部分。
| 套路 | 排序准则 | 证明锚点 |
|---|---|---|
| 区间调度（选最多） | 右端点升序 | 结束早→剩余空间最大 |
| 区间覆盖（最少区间） | 左端点升序 | 每步覆盖到最远 |
| Kruskal MST | 边权升序 | 交换论证 + 环性质 |
| Huffman | 频率最小优先 | 交换论证 |
| 最大数拼接（179） | a+b > b+a 字典序 | 该序是全序 + 传递性证明 |
Intervals · LC 435/452/56
// 435 无重叠区间：最少移除几个 func eraseOverlapIntervals(iv [][]int) int { sort.Slice(iv, func(i, j int) bool { return iv[i][1] < iv[j][1] // 右端点 }) keep, end := 0, int(-1<<62) for, in := range iv { if in[0] >= end { // 不重叠，保留 keep++ end = in[1] } } return len(iv) - keep } // 452 射气球：同款，ans = 保留的箭数 // 56 合并区间：按左端点排，相邻合并
要"选最多不相交区间"= 每次选结束最早的，给后面留最大空间。结束最早 = 右端点最小——这就是交换论证的锚点（第 3 页三步）。
435：移除最少 = 保留最多（补集转换）；452：一支箭爆所有重叠气球 = 按右端点分组计数；56：合并区间改按左端点排、相邻重叠就并——准则由问法决定。
435/452 的"相邻端点相触"算不算重叠：452 算（x=x 处可爆）、435 不算（end 相接不重叠）——题面一字之差，比较符变号，读完题先定比较符。
763 划分字母区间（每字母最后出现位置）、1024 视频拼接（最远覆盖）、1288 删除被覆盖区间。区间族占贪心 medium 题的大半。
Jump Game · LC 55/45
// 55 能否到达终点 func canJump(a []int) bool { reach := 0 for i := 0; i < len(a); i++ { if i > reach { return false } // i 可达时才更新 if i+a[i] > reach { reach = i + a[i] } if reach >= len(a)-1 { return true } } return true } // 45 最少跳跃次数：贪心分层 func jump(a []int) int { steps, end, far := 0, 0, 0 for i := 0; i < len(a)-1; i++ { if i+a[i] > far { far = i + a[i] } if i == end { // 本层用尽 steps++ end = far } } return steps }
维护 reach = 目前可达的最远下标：i > reach 说明有"断崖" → false；否则用 i+a[i] 扩张 reach。贪心性质：可达集合恰好是连续前缀，一个变量就够。
把"第 k 步可达的区间 [上一步 end+1, far]"看成一层：i 走到本层边界 end 时层数 +1、新边界 = far。等价于在隐式图上 BFS——每层取层内最远就是最优（交换论证）。
DP：dp[i] = min(dp[j]+1) 是 O(n²)；贪心利用"可达区间连续"的单调性直接 O(n)。发现单调结构 = 贪心机会。
45 的循环只到 len−1（最后一格不用再跳）；a[0]=0 且 n>1 时 55 返回 false——单元素数组恒 true，这两个 case 手推一遍。
Candy · Stock II · LC 455/135/122
规则=比左右邻居评分高就得多。单方向无法同时满足 → 两次遍历：左→右保证"比左邻多"，右→左保证"比右邻多"，取每位 max。
孩子胃口、饼干尺寸都升序，小饼干优先喂小胃口——两个指针谁小移谁。交换论证：最小饼干喂最小可满足的孩子不亏。
任意次交易的最大利润 = 所有正的相邻差之和：sum(max(0, a[i]−a[i−1]))。证明：任何多次交易的利润可拆成逐日差分，负差直接跳过——贪心解 = 上界 = 可达。
121（一次交易）贪心维护历史最低；122（无限次）涨跌幅求和；带冷冻/手续费的 309/714 就得回 状态机 DP——约束一复杂，贪心让位。
// 135 分发糖果：两次遍历 func candy(r []int) int { n := len(r) c := make([]int, n) for i := range c { c[i] = 1 } for i := 1; i < n; i++ { // 比左邻 if r[i] > r[i-1] { c[i] = c[i-1] + 1 } } for i := n - 2; i >= 0; i-- { // 比右邻 if r[i] > r[i+1] && c[i] <= c[i+1] { c[i] = c[i+1] + 1 } } sum := 0 for _, v := range c { sum += v } return sum } // 122 股票 II：正涨幅全吃 func maxProfit(p []int) int { ans := 0 for i := 1; i < len(p); i++ { if p[i] > p[i-1] { ans += p[i] - p[i-1] } } return ans }
When Greedy Lies
面值 [1, 3, 4] 找 6：贪心（每次拿最大）= 4+1+1 = 3 枚；最优 = 3+3 = 2 枚。局部"拿最大"在组合约束下互相打架。标准币制（1/5/10/50…）是特例，贪心恰好成立。
贪心选择性质被破坏：当前最优选择会锁死未来更优的组合。凡是"选择之间有复杂耦合"（组合、配对、资源竞争）的题，贪心都要先过反例这一关。
① 写贪心前先找反例（小 n 手推）；② 找不到反例 → 试交换论证；③ 证不出来 → 降级 DP 并说明"贪心在此无选择性质"。这条链展示了完整的决策过程。
零钱兑换（322，任意币制）、背包、任务调度带依赖、区间带权调度（权值耦合 → DP on 排序后区间）。
跳跃游戏 45 名义上"最少次数"（像 DP），但可达区间连续的单调结构让贪心 O(n)——发现单调/连续结构是升级为贪心的信号。
| 问题 | 贪心？ | 原因 |
|---|---|---|
| 标准币制找零 | ✓ | 币制结构保证 |
| 任意币制找零（322） | ✗ → DP | [1,3,4] 反例 |
| 区间调度 | ✓ | 交换论证 |
| 带权区间调度 | ✗ → DP | 权值破坏右端点准则 |
| 跳跃游戏 | ✓ | 可达区间连续 |
| 股票带冷冻 | ✗ → DP | 状态耦合 |
LeetCode Shortlist
| 部落 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 区间调度 | 435 无重叠区间 M · 452 射气球 M · 56 合并区间 M · 763 划分字母 M | 右端点/左端点准则的选择 |
| 跳跃游戏 | 55 E · 45 H · 1306 跳跃游戏 III M | 45 的分层贪心；1306 是 BFS |
| 分发/配对 | 455 分发饼干 E · 135 分糖果 H · 870 优势洗牌 M | 田忌赛马 = 排序配对贪心 |
| 序列扫描 | 122 股票 II M · 53 最大子数组 M · 376 摆动序列 M | 376 数拐点 = 峰谷计数 |
| 构造/拼接 | 179 最大数 M · 406 根据身高重建 H · 621 任务调度 M | 179 的比较器证明；406 从高到低插入 |
Cheat Sheet
| 套路 | 排序准则 | 证明锚点 |
|---|---|---|
| 区间调度（选最多） | 右端点升序 | 结束早 → 留给后面的空间最大 |
| 区间覆盖（最少区间） | 左端点升序 | 每步覆盖到最远 |
| 分发饼干（455） | 双升序 + 双指针 | 最小饼干喂最小可满足的孩子不亏 |
| 跳跃游戏 45 | 不排序，分层 | 第 k 步可达区间是一层，层内取最远 |
| Kruskal MST | 边权升序 | 交换论证 + 环性质 |
| Huffman 编码 | 频率最小优先 | 交换论证 |
1 · 先找反例。小 n 手推，试图构造一个让贪心非最优的输入。[1,3,4] 找 6 是标准武器——证伪比证明便宜，先做便宜的那件。
2 · 找不到反例就试交换论证。任取一个最优解，把它的第一个选择换成你的贪心选择，论证"换上去之后不会变差"。
3 · 证不出来就降级 DP。并主动说明"这里贪心没有选择性质"——这比硬交一份错误的贪心得分高得多。
4 · 反过来也别忘了。如果发现单调 / 连续结构（如可达区间连续），可以把 O(n²) 的 DP 升级成 O(n) 的贪心。
| 问题 | 贪心？ | 原因 |
|---|---|---|
| 标准币制找零 | ✓ | 币制本身的数学结构保证 |
| 任意币制找零（322） | ✗ → DP | [1,3,4] 找 6 反例 |
| 区间调度（435） | ✓ | 交换论证 |
| 带权区间调度 | ✗ → DP | 权值破坏了"右端点最小"准则 |
| 跳跃游戏（45） | ✓ | 可达区间连续（单调结构） |
| 股票带冷冻 / 手续费 | ✗ → DP | 状态耦合，需要状态机 DP |
Interview QA
先自答，再对照：每题先说出你的答案（哪怕只说关键词），再展开下面那行——卡住的那 30 秒才真正长记性。
选择性质（全局最优含贪心选择）+ 最优子结构（子问题独立）。前提须证明或反例，不能靠直觉。
任取最优解 → 第一步换成贪心选择（不更差）→ 归纳到底。最优解可被逐步"洗"成贪心解。
结束越早留给后面的空间越大——可交换论证锚定。按左端点排会先吃掉大区间（[1,100] 反例）。
同一骨架两种语义：435"end 相接不算重叠"（>= 保留）；452"端点相触可同爆"（> 保留）。一字之差。
第 k 步可达恰是连续区间 [end+1, far]，维护每层边界、层数即最少跳数。可达区间的连续性是贪心成立的关键。
币制 [1,3,4] 找 6：贪心 4+1+1 三枚 vs 最优 3+3 两枚。标准币制是特例——322 零钱兑换必须 DP。
利润可拆成相邻日差分之和，每段 ≤ max(0, 差值) → 正差之和是上界；逐日买卖恰好达到 → 贪心=最优。
是。按边权升序选、不成环就要：交换论证 + "环上最大边可删"性质可证最优（图 deck 展开）。
比较器 a+b vs b+a 字典序：需证全序与传递性（ab>ba, bc>cb ⇒ ac>ca）。证明完才能 sort。
"区间/调度/分配"+"每步选最优"+无耦合 → 先试贪心；有耦合 → DP。试探顺序：贪心 → DP → 回溯。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch15.4 · ch16（贪心策略） | 贪心选择性质与交换论证的形式化（活动选择/Huffman） |
| LeetCode 435/452/55/45/135/122/179 题解 | 各部落代表题与反例 |
| Cormen et al. · Huffman 证明；Tarjan · MST 交换论证 | 图论贪心的经典证明范例 |
| oi-wiki.org/basic/greedy | 贪心专题与常见反例（中文对照） |