02.8.1.1 贪心正确性证明与反例
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧
02.8.1.1-001 贪心算法的核心思想是什么?
一句话结论
贪心在每一步做出当前看来最优(局部最优)的选择,期望由此累积出全局最优解;选择一旦做出不回头,不需要枚举所有分支。
概念解释
- 局部最优:在当前状态下收益最大/代价最小的决策。
- 不可逆:选定后不保留其他分支,也不回溯撤销。
- 全局最优:最终方案在所有可行方案中达到最优目标。
原理流程
- 明确优化目标与可行决策集合。
- 确定每一步可比较的贪心指标(结束时间、单位代价、大小等)。
- 按指标做当前最优选择,缩小剩余问题。
- 重复直到问题耗尽,再用证明手段核对是否全局最优。
代码 / 示例
// 抽象流程:每步取候选中指标最优者,不回溯
List<Item> greedy(List<Item> candidates) {
List<Item> ans = new ArrayList<>();
while (!candidates.isEmpty()) {
Item pick = candidates.stream().min(byMetric).orElseThrow();
ans.add(pick);
candidates = remainAfter(pick, candidates);
}
return ans;
}
常见误区
- 误区:贪心就是“每次取最大/最小”;正解:指标必须由问题结构决定,且要能证明局部最优通向全局最优。
- 误区:贪心一定比 DP 快所以优先用;正解:先判断问题是否满足贪心条件,不满足时硬贪会得到错误答案。
追问
- Q:贪心需要保存所有分支吗? A:不需要,只沿当前最优路径推进,空间常优于回溯。
- Q:贪心答案可以是一个集合吗? A:可以,每次向结果集加入当前最优元素,如区间调度、哈夫曼。
02.8.1.1-002 贪心与动态规划的本质区别是什么?
一句话结论
DP 保留每个子问题的最优解并枚举所有可行决策,允许状态回退与比较;贪心只做一条局部最优路径,不比较备选决策;判断关键是当前选择是否影响后续可选状态、能否被后续决策纠正。
概念解释
- DP:最优子结构 + 重叠子问题,状态转移枚举末步决策。
- 贪心:贪心选择性质 + 最优子结构,每步不可撤销。
- 选择依赖性:若选了某项会改变后续可用集合的结构,贪心风险高。
原理流程
- 问:当前最优选择是否会让后续无法补救?
- 会 → 用 DP 保留状态;不会且可证明 → 贪心。
- 典型对照:01 背包用 DP,区间调度用贪心。
代码 / 图示
DP:dp[状态] = 枚举所有决策取最优;保留多条路径
贪心:每步取当前最优,路径唯一,不回退
常见误区
- 误区:贪心是 DP 的简化版,都能互相转换;正解:不满足贪心选择性质时,简化会丢失最优解。
- 误区:DP 一定比贪心慢;正解:复杂度取决于状态数与转移代价,不能一概而论。
追问
- Q:01 背包为什么不能按性价比贪心? A:物品不可拆分,性价比最高的组合未必容量利用率最优,需 DP 枚举取舍。
- Q:完全背包可以贪心吗? A:仍需 DP;只有物品可任意拆分(分数背包)才按单位价值贪心。
02.8.1.1-003 交换论证怎么证明贪心正确?
一句话结论
交换论证:取任一最优解,把其中第一个与贪心选择不同的决策,替换为贪心选择,解不会变差;反复交换后最优解可被贪心解覆盖,从而贪心最优。
概念解释
- 最优解:存在一个达到目标上界/下界的方案。
- 交换:在不破坏可行性的前提下替换决策。
- 不劣性:替换后目标值不恶化。
原理流程
- 设存在最优解 O,贪心解 G。
- 找 O 中第一个与 G 不同的决策。
- 用 G 的决策替换 O 中对应决策,论证仍可行且目标不劣。
- 重复至 O 与 G 一致,说明 G 不劣于最优,即最优。
代码 / 示例
区间调度:最优解中第一个区间若结束更晚,换成结束最早的可行区间,剩余空间不减少,解不劣。
常见误区
- 误区:交换后只看当前决策;正解:必须论证替换不破坏后续可行性。
- 误区:交换论证适用于所有贪心;正解:仅当决策可互换且指标单调时成立。
追问
- Q:交换论证属于哪种证明? A:构造性证明,把最优解逐步改造成贪心解。
- Q:若替换后目标变差怎么办? A:说明该贪心指标不成立,需换指标或改用 DP。
02.8.1.1-004 归纳法怎么证明贪心正确?
一句话结论
归纳法:基准情形小规模成立;假设前 k 步贪心得到的是剩余问题的最优决策序列,证明第 k+1 步贪心选择后剩余子问题仍可最优求解,从而整体最优。
概念解释
- 归纳假设:前序决策序列最优。
- 归纳步:当前贪心选择不破坏剩余子问题的最优性。
- 与交换论证互补:一个向前构造,一个向后改造。
原理流程
- 验证空/最小规模结论成立。
- 假设规模 n-1 成立。
- 证明规模 n 下贪心选择后,剩余 n-1 子问题可由归纳假设最优解决。
- 合并得到规模 n 最优。
代码 / 示例
Huffman:合并两个最小权节点,剩余问题规模减一,归纳假设剩余合并最优。
常见误区
- 误区:归纳只证明当前步最优;正解:必须证明剩余子问题结构不变、可复用归纳假设。
- 误区:把归纳假设写成“贪心全局最优”循环论证;正解:假设只覆盖前序规模。
追问
- Q:归纳与交换论证怎么选? A:决策可互换用交换论证;子问题规模递减用归纳。
- Q:证明不出来怎么办? A:先找反例,可能问题本身不可贪心。
02.8.1.1-005 贪心选择性质与最优子结构分别指什么?
一句话结论
最优子结构:全局最优解包含子问题的最优解;贪心选择性质:每步做出的局部最优选择不依赖未来决策,且选完后剩余问题仍是同类子问题;两者同时满足才可贪心。
概念解释
- 最优子结构:子结构最优可向上合并。
- 贪心选择性质:当前决策可独立判定,不需看后续。
- 缺最优子结构:连 DP 都不适用;缺选择性质:只能 DP。
原理流程
- 验证子问题最优解能拼成全局最优。
- 验证当前步指标选择不会使后续子问题失去最优性。
- 两者齐备 → 贪心;缺选择性质 → DP。
代码 / 图示
区间调度:选结束最早区间后,剩余区间仍是同型调度问题(选择性质 + 最优子结构)
常见误区
- 误区:有最优子结构就能贪心;正解:还需贪心选择性质,否则用 DP。
- 误区:贪心选择性质可以事后补;正解:必须在决策当下成立,不能依赖回溯修正。
追问
- Q:DP 依赖最优子结构吗? A:依赖,但 DP 不要求贪心选择性质。
- Q:两个性质都不满足怎么办? A:考虑回溯枚举、图算法或数学结论。
02.8.1.1-006 01 背包为什么是贪心失败的经典反例?
一句话结论
01 背包物品不可拆分,按单位价值贪心可能装入高性价比但体积大的物品,挤掉多个低性价比但组合更满的物品;容量约束下局部最优组合不等于全局最优,必须 DP。
概念解释
- 不可拆分:物品要么全取要么不取。
- 容量利用率:总价值还受剩余空间能否被填满影响。
- 分数背包:物品可拆分,按单位价值贪心正确。
原理流程
- 容量 W,物品 (重量 w, 价值 v)。
- 按 v/w 降序取,可能剩余空间装不下下一件。
- 反例:高性价比大件挤占空间,组合价值低于另一种取舍。
- 正确做法:dp[i][w] 枚举取/不取。
代码 / 示例
// 贪心(错误示范,仅说明反例):按单位价值排序后依次装
// 正确:01 背包 DP,见 02.7.1.2 背包问题
常见误区
- 误区:把分数背包结论套到 01 背包;正解:可拆分性改变贪心适用性。
- 误区:性价比排序后用 DP 仍是贪心;正解:排序只是预处理,决策仍由 DP 枚举。
追问
- Q:分数背包为什么贪心正确? A:物品可切分,剩余容量按单位价值继续填充,无空间浪费问题。
- Q:01 背包贪心错在哪一步? A:当前选择锁定物品后无法再比较被挤掉物品的组合收益。
02.8.1.1-007 找零问题什么时候贪心失效?
一句话结论
当币值体系满足规范(如可被相邻面额整除或构成 canonical 系统)时,大面额优先贪心正确;币值不规范时,优先用大钞可能凑不出最少张数,需 DP 求最少硬币数。
概念解释
- 规范币制:大面额与小面额存在整除/覆盖关系。
- 非规范:局部少用张数导致剩余金额难以凑。
- 最少张数:典型可 DP 的完全背包问题。
原理流程
- 币值降序,贪心每次取最大不超过剩余金额的面额。
- 非规范体系下可能剩余金额只能用多张小币,总张数更多。
- 正确做法:零钱兑换 DP,见 02.7.1.2。
代码 / 示例
// 反例方向:面额 {1, 3, 4},金额 6
// 贪心:4+1+1 = 3 张;最优:3+3 = 2 张
常见误区
- 误区:人民币体系经验可推广到任意币值;正解:必须先确认币制规范性。
- 误区:贪心凑不出来就是无解;正解:可能只是贪心策略错误,DP 存在可行解。
追问
- Q:如何判断币制是否 canonical? A:理论上可比对贪心与 DP 在各金额下的结果,面试中按题意举例反例即可。
- Q:无限取币对应哪种 DP? A:完全背包,求最少件数。
02.8.1.1-008 常见可贪心题型有哪些?
一句话结论
区间调度、区间合并、活动选择、分数背包、哈夫曼编码、最小生成树、Dijkstra 单源最短路、跳跃类可达性、糖果分发、任务排队(截止时间 + 罚金)等;共性是指标明确且决策可排序后依次确定。
概念解释
- 区间类:按结束/开始时间排序。
- 合并类:按权值或代价聚合。
- 图类:基于最优子结构的边/节点选择。
原理流程
- 归类题型,识别排序键或聚合规则。
- 套用对应贪心模式。
- 用交换论证核对关键步骤。
代码 / 图示
区间调度 → 结束时间升序;Huffman → 每次合并最小两堆;MST → 最小边/最近点
常见误区
- 误区:见到“最大/最少”就贪心;正解:先验证选择性质。
- 误区:把 Dijkstra 当纯贪心无证明;正解:其正确性基于边权非负与最短距离子结构。
追问
- Q:Dijkstra 为什么不能用于负权? A:已确定的最短距离可能被负权边推翻,贪心选择不再不可逆。
- Q:任务调度按什么排序? A:截止时间或单位罚金,视题目目标而定。
02.8.1.1-009 局部最优一定推出全局最优吗?
一句话结论
不一定;只有满足贪心选择性质且局部选择不损害后续可行性时,局部最优才累积为全局最优;存在反馈耦合、容量挤占、顺序依赖的问题上,局部最优可能是陷阱。
概念解释
- 反馈耦合:当前选择改变后续可选集合。
- 局部陷阱:当前收益高但堵死高收益路径。
- 校验手段:反例 + 证明。
原理流程
- 写出贪心选择。
- 构造小规模反例尝试推翻。
- 推不翻再用交换/归纳论证。
代码 / 示例
每步选当前最大价值 → 若后续路径被堵,整体收益下降
常见误区
- 误区:直觉上合理就当贪心正确;正解:面试必须给出证明或反例判断。
- 误区:局部最优解多走几步能修正;正解:贪心不可逆,修正需回溯,已不是贪心。
追问
- Q:怎么快速找反例? A:从小规模(3 个元素以内)枚举排列组合观察指标冲突。
- Q:局部最优有什么参考价值? A:可作为贪心候选,也可作为 DP 的边界对比。
02.8.1.1-010 贪心与排序是什么关系?
一句话结论
多数贪心先按某指标排序,再依次决策;排序键本身就是贪心假设的载体——键选错,后续决策再正确也得不到最优;排序是手段,指标选择与证明才是核心。
概念解释
- 排序键:结束时间、开始时间、重量、单位价值、截止时间。
- 指标一致性:同一题可能有多个键,需按目标选对。
- 稳定排序影响并列元素处理。
原理流程
- 确定优化目标(数量最多、代价最小、收益最大)。
- 推导应排序的指标。
- 排序后线性扫描决策。
代码 / 示例
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1])); // 区间调度按结束
常见误区
- 误区:所有贪心都先排序;正解:哈夫曼用优先队列动态取最小,不一次性排序。
- 误区:排序键可随意互换;正解:结束时间与开始时间对应不同问题,混用会出错。
追问
- Q:区间合并按什么排序? A:按开始时间升序,维护当前右边界。
- Q:排序复杂度计入总复杂度吗? A:计入,通常 O(n log n) 为瓶颈。
02.8.1.1-011 区间调度贪心为什么按结束时间排序?
一句话结论
结束最早的区间为后续区间留出最多剩余时间,兼容性最好;交换论证证明替换成结束最早者不会减少可选数量,因此可得到最多不重叠区间数。
概念解释
- 兼容性:后一区间开始不早于前一区间结束。
- 剩余空间:结束越早,右侧可安排区间越多。
- 目标:区间数量最大。
原理流程
- 按结束时间升序。
- 选结束最早且与已选不冲突的区间。
- 更新结束边界,扫描剩余区间。
代码 / 示例
int maxNonOverlap(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 0, end = Integer.MIN_VALUE;
for (int[] it : intervals) {
if (it[0] >= end) { count++; end = it[1]; }
}
return count;
}
常见误区
- 误区:按开始时间最早选能放最多区间;正解:开始早但跨度大的区间会挤占后续空间。
- 误区:区间端点相等算冲突;正解:按题意判断,通常闭区间相接(start >= end)不算重叠。
追问
- Q:最少移除多少区间使剩余不重叠? A:总数 - 最多不重叠区间数。
- Q:区间覆盖问题按什么排? A:覆盖目标长度时常按开始排序并延长右边界。
02.8.1.1-012 哈夫曼编码的贪心正确性体现在哪?
一句话结论
每次合并权值最小的两个节点,使高频字符编码短、低频字符编码长;归纳可证合并后剩余问题仍是同型最优合并问题,因此总编码长度最小。
概念解释
- 权值:字符出现频率。
- 合并代价:两堆权值之和计入总路径长度。
- 最优子结构:合并后的新堆与其余节点继续最优合并。
原理流程
- 所有字符入最小堆。
- 弹出最小两堆合并,新权值入堆。
- 重复到剩一堆,构建编码树。
代码 / 示例
// 优先队列:poll 两次合并,offer 新节点
// 总代价 = 每次合并权值之和累加
常见误区
- 误区:哈夫曼按字符大小排序;正解:按频率(权值)动态合并。
- 误区:合并代价只算最终根权值;正解:每次合并的新权值都要计入带权路径长度。
追问
- Q:Huffman 是前缀编码吗? A:是,字符都在叶子节点,任一编码不是另一编码前缀。
- Q:时间复杂度? A:O(n log n),堆操作每次 O(log n),共 n-1 次合并。
02.8.1.1-013 最小生成树为什么能用贪心?
一句话结论
MST 中每条边的选择满足割性质:跨越任意割的最轻边必在某棵 MST 中;Kruskal 按边权升序选不形成环的边,Prim 从当前树取最小跨边,两者都是贪心在割性质上的应用。
概念解释
- 割:顶点划分;跨边:两端分属两侧。
- 割性质:最轻跨边可纳入 MST。
- 环性质:环上最重边可排除。
原理流程
- Kruskal:边升序,并查集判断不成环则加入。
- Prim:从起点扩展,优先队列维护最小跨边。
- 边数达到 n-1 停止。
代码 / 示例
Kruskal:排序 + 并查集;Prim:点集扩展 + 最小堆
常见误区
- 误区:MST 是图中边权和最小的路径集合;正解:是连通所有顶点的无环最小权生成树。
- 误区:连通分量不一时 Kruskal 仍能得到树;正解:需图连通,否则得到森林。
追问
- Q:Kruskal 与 Prim 适用场景? A:稀疏图 Kruskal 排序 + 并查集;稠密图 Prim 邻接矩阵更省。
- Q:MST 唯一吗? A:边权并列时可能多棵 MST,总权值相同。
02.8.1.1-014 跳跃游戏的贪心正确性怎么理解?
一句话结论
维护当前可达最远下标;扫描到 i 时若 i 不可达(i > 最远)则失败,否则用 i+nums[i] 更新最远;最远边界只增不减,覆盖所有可达位置,因此到达最后位置的判定正确。
概念解释
- 可达区间:从起点能一步/多步到达的下标范围。
- 最远推进:每步从可达区间内更新可达边界。
- 不可逆:边界单调右扩,无需回退。
原理流程
- farthest = 0。
- 遍历 i,不可达则返回 false。
- 更新 farthest,达到末位返回 true。
代码 / 示例
boolean canJump(int[] nums) {
int far = 0;
for (int i = 0; i < nums.length; i++) {
if (i > far) return false;
far = Math.max(far, i + nums[i]);
if (far >= nums.length - 1) return true;
}
return true;
}
常见误区
- 误区:只记录当前位置能跳到的下一格;正解:要维护整个可达区间的最远边界。
- 误区:遇到 0 就失败;正解:0 只是不可再向前跳,若已被之前的跨度覆盖仍可达。
追问
- Q:最少跳几次怎么做? A:按 BFS 分层,维护当前层右边界与下一步最远边界。
- Q:时间复杂度? A:O(n),空间 O(1)。
02.8.1.1-015 贪心指标选错会出现什么反例?
一句话结论
同一问题换排序键(按开始 vs 按结束、按重量 vs 按价值)会得到不同结果;指标与优化目标不匹配时,贪心可能得到明显劣解,因此面试必须先讲清“为什么用这个键”。
概念解释
- 指标错位:决策标准与目标不一致。
- 可观察症状:小规模用例即可暴露次优。
- 修复:回到交换论证重新选键。
原理流程
- 列出候选指标。
- 小规模构造用例对比各指标结果。
- 选满足不劣性论证的指标。
代码 / 图示
区间调度:结束时间 √;开始时间 ×;最短跨度 √(部分变体)
常见误区
- 误区:题目要求“最少区间”就按长度排序;正解:目标不同,键不同,需具体论证。
- 误区:并列元素顺序无所谓;正解:并列时的二级键可能影响后续可行性。
追问
- Q:怎么判断指标是否够用? A:交换论证中替换后剩余空间/资源不减少。
- Q:指标选错能用调试发现吗? A:小规模反例最直接,复杂用例掩盖问题。
02.8.1.1-016 贪心解需要回溯撤销吗?
一句话结论
标准贪心不撤销已做选择;若发现需要撤销重选,说明该题不适合贪心,应改用 DP、回溯或带撤销的堆算法;贪心路径唯一是其核心特征。
概念解释
- 不可逆选择:一旦加入结果即固定。
- 撤销型算法:如 Prim 可换边,但那是算法内部状态,不是回溯分支。
- 边界:部分贪心用堆动态替换已选元素,需区分。
原理流程
- 判断已选决策是否还可能被后续替换。
- 可能替换 → 不是纯贪心,按对应数据结构题处理。
- 不可替换 → 贪心路径推进。
代码 / 示例
纯贪心:选入即固定;堆替换类:候选集动态更新,仍可归为贪心变体
常见误区
- 误区:贪心写错了靠撤销补救;正解:补撤销就变成搜索/DP,应换方法。
- 误区:贪心结果一定唯一;正解:并列最优可能有多解,贪心给出其一。
追问
- Q:带反悔的贪心存在吗? A:存在,如优先队列维护已选并在超限时弹出最差项,但前提是可证明替换不破坏最优。
- Q:反悔贪心和 DP 区别? A:反悔只替换最差项,仍保留贪心指标,不枚举完整状态。
02.8.1.1-017 贪心算法的复杂度有什么特征?
一句话结论
常见贪心以一次排序或一次堆操作 + 线性扫描为主,时间多为 O(n log n) 或 O(n),空间 O(1)~O(n);复杂度瓶颈通常在排序或优先队列,决策扫描本身是线性的。
概念解释
- 排序型:O(n log n) 时间,O(1) 额外空间(原地排序)。
- 堆型:O(n log n),堆空间 O(n)。
- 线性型:O(n) 扫描,O(1) 空间。
原理流程
- 识别排序或堆预处理。
- 统计扫描/弹出次数。
- 合并各阶段复杂度。
代码 / 图示
排序贪心:O(n log n);堆贪心:O(n log n);扫描贪心:O(n)
常见误区
- 误区:贪心空间一定 O(1);正解:堆、候选集合、结果集都要占空间。
- 误区:贪心复杂度与 DP 对比时忽略排序;正解:排序常是主要开销。
追问
- Q:Huffman 复杂度? A:O(n log n) 时间,O(n) 堆空间。
- Q:线性扫描贪心还能优化吗? A:已到 Ω(n) 下界,除非输入有序。
02.8.1.1-018 面试中如何论证一个贪心是否成立?
一句话结论
先给出贪心策略与指标,再用交换论证或归纳法说明不劣性,最后主动给一个易混淆的反例边界;讲不清证明时明确标注该题更稳妥的替代方法(DP/搜索)。
概念解释
- 策略先行:指标与选择规则。
- 证明兜底:交换/归纳。
- 反例意识:主动指出失效场景。
原理流程
- 陈述目标与可行决策。
- 给出贪心选择规则。
- 论证局部最优不损害剩余问题。
- 说明边界与失败情形。
代码 / 示例
话术:按结束时间排序 → 交换不减少剩余空间 → 反例:按开始时间会劣
常见误区
- 误区:直接写代码跳过证明;正解:面试先讲清“为什么这样贪”。
- 误区:证明用“显然”带过;正解:至少给出交换或归纳的关键一步。
追问
- Q:证明不出来怎么办? A:说明存疑,给出 DP/搜索保底方案并标注复杂度。
- Q:面试官追问反例怎么答? A:回到容量挤占、顺序依赖两类经典失效场景。
02.8.1.1-019 贪心与优先队列怎么配合?
一句话结论
当候选集需要动态取当前最优(最小/最大)且元素随过程加入时,用优先队列维护候选,每次弹出最优决策,再把新生成的候选入队;典型如 Huffman、Prim、任务调度。
概念解释
- 动态候选:新元素在决策过程中产生。
- 堆顶最优:O(log n) 取极值。
- 批量排序无法覆盖动态加入。
原理流程
- 初始化候选入堆。
- 弹出最优,更新状态。
- 产生新候选入堆,重复。
代码 / 示例
PriorityQueue<Item> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.metric));
while (!pq.isEmpty()) {
Item cur = pq.poll();
// 决策
pq.offer(next);
}
常见误区
- 误区:堆中重复放入同一候选导致膨胀;正解:按需去重或接受过期项并惰性剔除。
- 误区:堆顶元素就是最终答案;正解:堆只保证当前最优,全局结论需算法终止时得出。
追问
- Q:堆贪心时间复杂度? A:每次入/出堆 O(log n),共 O(n log n)。
- Q:什么题不用堆? A:候选固定可一次性排序的,用排序 + 线性扫描更简单。
02.8.1.1-020 贪心题的常见错误来源有哪些?
一句话结论
错误来源集中在:指标选错、排序键方向反、边界端点处理错、把不可拆分问题当可拆分、未验证选择性质直接套用模板;复盘时按这五类逐项核对。
概念解释
- 指标:优化目标映射的键。
- 方向:升序/降序与目标匹配。
- 边界:相等端点、空输入、单元素。
原理流程
- 核对排序指标与目标一致性。
- 核对升降序方向。
- 核对端点与空边界。
- 回查可拆分性与选择性质。
代码 / 图示
指标 → 方向 → 端点 → 可拆分性 → 证明,逐项排查
常见误区
- 误区:照搬模板不看题意;正解:每道题先重述目标与约束。
- 误区:复杂度报成 O(n) 忽略排序;正解:把预处理开销计入。
追问
- Q:贪心题最容易漏的边界是什么? A:相等端点是否冲突、空数组、只有一个元素。
- Q:复盘贪心题记什么? A:排序键、证明关键步、反例与失效场景。