罗罗编程学习记录
本页内容 展开查看

02.8.1.1 贪心正确性证明与反例

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧

02.8.1.1-001 贪心算法的核心思想是什么?

一句话结论

贪心在每一步做出当前看来最优(局部最优)的选择,期望由此累积出全局最优解;选择一旦做出不回头,不需要枚举所有分支。

概念解释

  • 局部最优:在当前状态下收益最大/代价最小的决策。
  • 不可逆:选定后不保留其他分支,也不回溯撤销。
  • 全局最优:最终方案在所有可行方案中达到最优目标。

原理流程

  1. 明确优化目标与可行决策集合。
  2. 确定每一步可比较的贪心指标(结束时间、单位代价、大小等)。
  3. 按指标做当前最优选择,缩小剩余问题。
  4. 重复直到问题耗尽,再用证明手段核对是否全局最优。

代码 / 示例

// 抽象流程:每步取候选中指标最优者,不回溯
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:最优子结构 + 重叠子问题,状态转移枚举末步决策。
  • 贪心:贪心选择性质 + 最优子结构,每步不可撤销。
  • 选择依赖性:若选了某项会改变后续可用集合的结构,贪心风险高。

原理流程

  1. 问:当前最优选择是否会让后续无法补救?
  2. 会 → 用 DP 保留状态;不会且可证明 → 贪心。
  3. 典型对照:01 背包用 DP,区间调度用贪心。

代码 / 图示

DP:dp[状态] = 枚举所有决策取最优;保留多条路径
贪心:每步取当前最优,路径唯一,不回退

常见误区

  • 误区:贪心是 DP 的简化版,都能互相转换;正解:不满足贪心选择性质时,简化会丢失最优解。
  • 误区:DP 一定比贪心慢;正解:复杂度取决于状态数与转移代价,不能一概而论。

追问

  • Q:01 背包为什么不能按性价比贪心? A:物品不可拆分,性价比最高的组合未必容量利用率最优,需 DP 枚举取舍。
  • Q:完全背包可以贪心吗? A:仍需 DP;只有物品可任意拆分(分数背包)才按单位价值贪心。

02.8.1.1-003 交换论证怎么证明贪心正确?

一句话结论

交换论证:取任一最优解,把其中第一个与贪心选择不同的决策,替换为贪心选择,解不会变差;反复交换后最优解可被贪心解覆盖,从而贪心最优。

概念解释

  • 最优解:存在一个达到目标上界/下界的方案。
  • 交换:在不破坏可行性的前提下替换决策。
  • 不劣性:替换后目标值不恶化。

原理流程

  1. 设存在最优解 O,贪心解 G。
  2. 找 O 中第一个与 G 不同的决策。
  3. 用 G 的决策替换 O 中对应决策,论证仍可行且目标不劣。
  4. 重复至 O 与 G 一致,说明 G 不劣于最优,即最优。

代码 / 示例

区间调度:最优解中第一个区间若结束更晚,换成结束最早的可行区间,剩余空间不减少,解不劣。

常见误区

  • 误区:交换后只看当前决策;正解:必须论证替换不破坏后续可行性。
  • 误区:交换论证适用于所有贪心;正解:仅当决策可互换且指标单调时成立。

追问

  • Q:交换论证属于哪种证明? A:构造性证明,把最优解逐步改造成贪心解。
  • Q:若替换后目标变差怎么办? A:说明该贪心指标不成立,需换指标或改用 DP。

02.8.1.1-004 归纳法怎么证明贪心正确?

一句话结论

归纳法:基准情形小规模成立;假设前 k 步贪心得到的是剩余问题的最优决策序列,证明第 k+1 步贪心选择后剩余子问题仍可最优求解,从而整体最优。

概念解释

  • 归纳假设:前序决策序列最优。
  • 归纳步:当前贪心选择不破坏剩余子问题的最优性。
  • 与交换论证互补:一个向前构造,一个向后改造。

原理流程

  1. 验证空/最小规模结论成立。
  2. 假设规模 n-1 成立。
  3. 证明规模 n 下贪心选择后,剩余 n-1 子问题可由归纳假设最优解决。
  4. 合并得到规模 n 最优。

代码 / 示例

Huffman:合并两个最小权节点,剩余问题规模减一,归纳假设剩余合并最优。

常见误区

  • 误区:归纳只证明当前步最优;正解:必须证明剩余子问题结构不变、可复用归纳假设。
  • 误区:把归纳假设写成“贪心全局最优”循环论证;正解:假设只覆盖前序规模。

追问

  • Q:归纳与交换论证怎么选? A:决策可互换用交换论证;子问题规模递减用归纳。
  • Q:证明不出来怎么办? A:先找反例,可能问题本身不可贪心。

02.8.1.1-005 贪心选择性质与最优子结构分别指什么?

一句话结论

最优子结构:全局最优解包含子问题的最优解;贪心选择性质:每步做出的局部最优选择不依赖未来决策,且选完后剩余问题仍是同类子问题;两者同时满足才可贪心。

概念解释

  • 最优子结构:子结构最优可向上合并。
  • 贪心选择性质:当前决策可独立判定,不需看后续。
  • 缺最优子结构:连 DP 都不适用;缺选择性质:只能 DP。

原理流程

  1. 验证子问题最优解能拼成全局最优。
  2. 验证当前步指标选择不会使后续子问题失去最优性。
  3. 两者齐备 → 贪心;缺选择性质 → DP。

代码 / 图示

区间调度:选结束最早区间后,剩余区间仍是同型调度问题(选择性质 + 最优子结构)

常见误区

  • 误区:有最优子结构就能贪心;正解:还需贪心选择性质,否则用 DP。
  • 误区:贪心选择性质可以事后补;正解:必须在决策当下成立,不能依赖回溯修正。

追问

  • Q:DP 依赖最优子结构吗? A:依赖,但 DP 不要求贪心选择性质。
  • Q:两个性质都不满足怎么办? A:考虑回溯枚举、图算法或数学结论。

02.8.1.1-006 01 背包为什么是贪心失败的经典反例?

一句话结论

01 背包物品不可拆分,按单位价值贪心可能装入高性价比但体积大的物品,挤掉多个低性价比但组合更满的物品;容量约束下局部最优组合不等于全局最优,必须 DP。

概念解释

  • 不可拆分:物品要么全取要么不取。
  • 容量利用率:总价值还受剩余空间能否被填满影响。
  • 分数背包:物品可拆分,按单位价值贪心正确。

原理流程

  1. 容量 W,物品 (重量 w, 价值 v)。
  2. 按 v/w 降序取,可能剩余空间装不下下一件。
  3. 反例:高性价比大件挤占空间,组合价值低于另一种取舍。
  4. 正确做法: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 的完全背包问题。

原理流程

  1. 币值降序,贪心每次取最大不超过剩余金额的面额。
  2. 非规范体系下可能剩余金额只能用多张小币,总张数更多。
  3. 正确做法:零钱兑换 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 单源最短路、跳跃类可达性、糖果分发、任务排队(截止时间 + 罚金)等;共性是指标明确且决策可排序后依次确定。

概念解释

  • 区间类:按结束/开始时间排序。
  • 合并类:按权值或代价聚合。
  • 图类:基于最优子结构的边/节点选择。

原理流程

  1. 归类题型,识别排序键或聚合规则。
  2. 套用对应贪心模式。
  3. 用交换论证核对关键步骤。

代码 / 图示

区间调度 → 结束时间升序;Huffman → 每次合并最小两堆;MST → 最小边/最近点

常见误区

  • 误区:见到“最大/最少”就贪心;正解:先验证选择性质。
  • 误区:把 Dijkstra 当纯贪心无证明;正解:其正确性基于边权非负与最短距离子结构。

追问

  • Q:Dijkstra 为什么不能用于负权? A:已确定的最短距离可能被负权边推翻,贪心选择不再不可逆。
  • Q:任务调度按什么排序? A:截止时间或单位罚金,视题目目标而定。

02.8.1.1-009 局部最优一定推出全局最优吗?

一句话结论

不一定;只有满足贪心选择性质且局部选择不损害后续可行性时,局部最优才累积为全局最优;存在反馈耦合、容量挤占、顺序依赖的问题上,局部最优可能是陷阱。

概念解释

  • 反馈耦合:当前选择改变后续可选集合。
  • 局部陷阱:当前收益高但堵死高收益路径。
  • 校验手段:反例 + 证明。

原理流程

  1. 写出贪心选择。
  2. 构造小规模反例尝试推翻。
  3. 推不翻再用交换/归纳论证。

代码 / 示例

每步选当前最大价值 → 若后续路径被堵,整体收益下降

常见误区

  • 误区:直觉上合理就当贪心正确;正解:面试必须给出证明或反例判断。
  • 误区:局部最优解多走几步能修正;正解:贪心不可逆,修正需回溯,已不是贪心。

追问

  • Q:怎么快速找反例? A:从小规模(3 个元素以内)枚举排列组合观察指标冲突。
  • Q:局部最优有什么参考价值? A:可作为贪心候选,也可作为 DP 的边界对比。

02.8.1.1-010 贪心与排序是什么关系?

一句话结论

多数贪心先按某指标排序,再依次决策;排序键本身就是贪心假设的载体——键选错,后续决策再正确也得不到最优;排序是手段,指标选择与证明才是核心。

概念解释

  • 排序键:结束时间、开始时间、重量、单位价值、截止时间。
  • 指标一致性:同一题可能有多个键,需按目标选对。
  • 稳定排序影响并列元素处理。

原理流程

  1. 确定优化目标(数量最多、代价最小、收益最大)。
  2. 推导应排序的指标。
  3. 排序后线性扫描决策。

代码 / 示例

Arrays.sort(intervals, Comparator.comparingInt(a -> a[1])); // 区间调度按结束

常见误区

  • 误区:所有贪心都先排序;正解:哈夫曼用优先队列动态取最小,不一次性排序。
  • 误区:排序键可随意互换;正解:结束时间与开始时间对应不同问题,混用会出错。

追问

  • Q:区间合并按什么排序? A:按开始时间升序,维护当前右边界。
  • Q:排序复杂度计入总复杂度吗? A:计入,通常 O(n log n) 为瓶颈。

02.8.1.1-011 区间调度贪心为什么按结束时间排序?

一句话结论

结束最早的区间为后续区间留出最多剩余时间,兼容性最好;交换论证证明替换成结束最早者不会减少可选数量,因此可得到最多不重叠区间数。

概念解释

  • 兼容性:后一区间开始不早于前一区间结束。
  • 剩余空间:结束越早,右侧可安排区间越多。
  • 目标:区间数量最大。

原理流程

  1. 按结束时间升序。
  2. 选结束最早且与已选不冲突的区间。
  3. 更新结束边界,扫描剩余区间。

代码 / 示例

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 哈夫曼编码的贪心正确性体现在哪?

一句话结论

每次合并权值最小的两个节点,使高频字符编码短、低频字符编码长;归纳可证合并后剩余问题仍是同型最优合并问题,因此总编码长度最小。

概念解释

  • 权值:字符出现频率。
  • 合并代价:两堆权值之和计入总路径长度。
  • 最优子结构:合并后的新堆与其余节点继续最优合并。

原理流程

  1. 所有字符入最小堆。
  2. 弹出最小两堆合并,新权值入堆。
  3. 重复到剩一堆,构建编码树。

代码 / 示例

// 优先队列: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。
  • 环性质:环上最重边可排除。

原理流程

  1. Kruskal:边升序,并查集判断不成环则加入。
  2. Prim:从起点扩展,优先队列维护最小跨边。
  3. 边数达到 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] 更新最远;最远边界只增不减,覆盖所有可达位置,因此到达最后位置的判定正确。

概念解释

  • 可达区间:从起点能一步/多步到达的下标范围。
  • 最远推进:每步从可达区间内更新可达边界。
  • 不可逆:边界单调右扩,无需回退。

原理流程

  1. farthest = 0。
  2. 遍历 i,不可达则返回 false。
  3. 更新 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 按价值)会得到不同结果;指标与优化目标不匹配时,贪心可能得到明显劣解,因此面试必须先讲清“为什么用这个键”。

概念解释

  • 指标错位:决策标准与目标不一致。
  • 可观察症状:小规模用例即可暴露次优。
  • 修复:回到交换论证重新选键。

原理流程

  1. 列出候选指标。
  2. 小规模构造用例对比各指标结果。
  3. 选满足不劣性论证的指标。

代码 / 图示

区间调度:结束时间 √;开始时间 ×;最短跨度 √(部分变体)

常见误区

  • 误区:题目要求“最少区间”就按长度排序;正解:目标不同,键不同,需具体论证。
  • 误区:并列元素顺序无所谓;正解:并列时的二级键可能影响后续可行性。

追问

  • Q:怎么判断指标是否够用? A:交换论证中替换后剩余空间/资源不减少。
  • Q:指标选错能用调试发现吗? A:小规模反例最直接,复杂用例掩盖问题。

02.8.1.1-016 贪心解需要回溯撤销吗?

一句话结论

标准贪心不撤销已做选择;若发现需要撤销重选,说明该题不适合贪心,应改用 DP、回溯或带撤销的堆算法;贪心路径唯一是其核心特征。

概念解释

  • 不可逆选择:一旦加入结果即固定。
  • 撤销型算法:如 Prim 可换边,但那是算法内部状态,不是回溯分支。
  • 边界:部分贪心用堆动态替换已选元素,需区分。

原理流程

  1. 判断已选决策是否还可能被后续替换。
  2. 可能替换 → 不是纯贪心,按对应数据结构题处理。
  3. 不可替换 → 贪心路径推进。

代码 / 示例

纯贪心:选入即固定;堆替换类:候选集动态更新,仍可归为贪心变体

常见误区

  • 误区:贪心写错了靠撤销补救;正解:补撤销就变成搜索/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) 空间。

原理流程

  1. 识别排序或堆预处理。
  2. 统计扫描/弹出次数。
  3. 合并各阶段复杂度。

代码 / 图示

排序贪心: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/搜索)。

概念解释

  • 策略先行:指标与选择规则。
  • 证明兜底:交换/归纳。
  • 反例意识:主动指出失效场景。

原理流程

  1. 陈述目标与可行决策。
  2. 给出贪心选择规则。
  3. 论证局部最优不损害剩余问题。
  4. 说明边界与失败情形。

代码 / 示例

话术:按结束时间排序 → 交换不减少剩余空间 → 反例:按开始时间会劣

常见误区

  • 误区:直接写代码跳过证明;正解:面试先讲清“为什么这样贪”。
  • 误区:证明用“显然”带过;正解:至少给出交换或归纳的关键一步。

追问

  • Q:证明不出来怎么办? A:说明存疑,给出 DP/搜索保底方案并标注复杂度。
  • Q:面试官追问反例怎么答? A:回到容量挤占、顺序依赖两类经典失效场景。

02.8.1.1-019 贪心与优先队列怎么配合?

一句话结论

当候选集需要动态取当前最优(最小/最大)且元素随过程加入时,用优先队列维护候选,每次弹出最优决策,再把新生成的候选入队;典型如 Huffman、Prim、任务调度。

概念解释

  • 动态候选:新元素在决策过程中产生。
  • 堆顶最优:O(log n) 取极值。
  • 批量排序无法覆盖动态加入。

原理流程

  1. 初始化候选入堆。
  2. 弹出最优,更新状态。
  3. 产生新候选入堆,重复。

代码 / 示例

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 贪心题的常见错误来源有哪些?

一句话结论

错误来源集中在:指标选错、排序键方向反、边界端点处理错、把不可拆分问题当可拆分、未验证选择性质直接套用模板;复盘时按这五类逐项核对。

概念解释

  • 指标:优化目标映射的键。
  • 方向:升序/降序与目标匹配。
  • 边界:相等端点、空输入、单元素。

原理流程

  1. 核对排序指标与目标一致性。
  2. 核对升降序方向。
  3. 核对端点与空边界。
  4. 回查可拆分性与选择性质。

代码 / 图示

指标 → 方向 → 端点 → 可拆分性 → 证明,逐项排查

常见误区

  • 误区:照搬模板不看题意;正解:每道题先重述目标与约束。
  • 误区:复杂度报成 O(n) 忽略排序;正解:把预处理开销计入。

追问

  • Q:贪心题最容易漏的边界是什么? A:相等端点是否冲突、空数组、只有一个元素。
  • Q:复盘贪心题记什么? A:排序键、证明关键步、反例与失效场景。