贪心算法
🧠 一、贪心的核心定义
贪心算法是一种在每一步都做出局部最优选择，最终期望获得全局最优解的方法。
使用前提：
必须满足「局部最优 = 全局最优」，否则贪心可能不是正确解法。
🔍 二、判断是否可以贪心的典型信号
| 判断信号 | 说明 |
|---|---|
| ✅ 排序后有策略可选 | 按区间左/右/结束时间排序、按字典序等 |
| ✅ 选择之间互不影响 | 子问题没有依赖，不选一个不会影响后续 |
| ✅ 无需回溯历史 | 当前选完之后无需回头 |
| ✅ 问题目标是「最小/最大/能否/最多」 | 常见在调度类、构造类题目中 |
💡 三、常见贪心策略与经典题型
| 题型 | 贪心策略 | 示例题目（Leetcode） |
|---|---|---|
| 区间调度 | 按结束时间排序，选不冲突的最多 | 435. 无重叠区间 |
| 跳跃游戏 | 每一步尽量跳得远 | 55. Jump Game / 45. Jump Game II |
| 字符串构造 | 局部最小字母优先、单调栈维护字典序 | 316. 去除重复字母 |
| 零钱找零 | 从大面额向小面额选（注意反例） | 860. 柠檬水找零 |
| 频率冲突 | 减少冲突频次 | 1647. 删除字符使频次唯一 |
| 多任务调度 | 按结束时间/负载等排序 | 253. 会议室 II |
| 区间合并 | 按起点排序合并重叠区间 | 56. Merge Intervals |
| 装箱问题 | 优先选单位价值高的 | 类似背包问题的变种 |
📚 四、推荐练习题目
| Leetcode 题号 | 标题 | 贪心策略 |
|---|---|---|
| 455 | 分发饼干 | 小饼干喂小胃口 |
| 435 | 无重叠区间 | 结束时间排序 |
| 55 / 45 | Jump Game I / II | 尽量跳远 |
| 134 | 加油站 | 净油量分析 |
| 406 | 根据身高重建队列 | 高的先排，按插入序处理 |
| 763 | 划分字母区间 | 尽量延长当前分段直到包含所有字符 |
| 621 | 任务调度器 | 贪心找频次最大任务 |
| 1647 | 删除字符使频次唯一 | 贪心频率递减+哈希 |
❗ 五、常见误区
| 误区 | 说明 |
|---|---|
| ❌ 所有最小/最大问题都能贪心 | 若问题有依赖关系，需用动态规划 |
| ❌ 贪心算法没有模板只能硬猜 | 虽无统一模板，但常见场景有套路 |
| ❌ 贪心和动态规划完全互斥 | 有些题目局部用贪心能优化 DP 的子问题 |
✅ 总结口诀
能排序就排序，
能局部选就选，
能不回头就不回，
目标问最多/最少/是否能做到，很可能是贪心。
1647. 字符频次唯一的最小删除次数
给定一个字符串 s，你可以通过从字符串中删除一些字符使得剩下的字符串满足如下条件： 所有字符出现的次数都不相同 返回你需要删除的最少字符数，使得最终字符串满足要求。 输入: s = “aaabbbcc” 输出: 2 解释: 你可以删除两个 ‘b’ 或者一个 ‘b’ 和一个 ‘c’，使得每个字符出现次数唯一。
1from collections import Counter
2def minDeletions(self, s):
3 c = Counter(s)
4 used = {}
5 count = 0
6 for char, freq in c.items():
7
8 while freq > 0 and freq in used:
9 freq -= 1
10 count += 1
11
12 used[freq] = True
13 return count