加载中…
应用场景：区间调度 · Huffman · Dijkstra
交互式动画演示，可调整参数并单步执行。
全屏打开贪心（Greedy） 是一种在每一步都采取当前状态下最优选择的算法策略，希望通过局部最优得到全局最优。
graph LR S[起点] -->|选局部最优| N1[下一步] N1 -->|选局部最优| N2[再下一步] N2 -->|到达目标| G[目标] Other[其他路径] -.X.-> G
关键：每一步不可撤销，像下棋。
它和 DP 的关键区别：
贪心不是万能的——用错地方会得到错误答案。判断依据有两个：
一个全局最优解，可以通过一系列局部最优选择得到。
问题的最优解包含子问题的最优解。
注意：这两个性质必须同时成立。只满足一个的，要么是错的贪心，要么其实是 DP。
问题：n 个区间 [s_i, e_i]，选最多的互不重叠区间。
贪心策略：按结束时间排序，每次选结束最早的。
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int ans = 0, lastEnd = Integer.MIN_VALUE;
for (int[] it : intervals) {
if (it[0] >= lastEnd) {
ans++;
lastEnd = it[1];
}
}
return ans;为什么对？ 证明思路（交换论证）：
假设贪心选了第一个结束最早的区间
I_1，而某个最优解选了I_1'（结束更晚）。 因为I_1比I_1'结束早，用I_1替换I_1'后剩余空间更大，剩下的可选区间只会更多不会更少。 因此存在最优解包含I_1，递归对剩下区间成立。
int jumps = 0, end = 0, farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == end) {
jumps++;
end = farthest;
}
}
return jumps;经典题型：将孩子的需求和糖果大小排序，双指针贪心。
// 455. 分发饼干
Arrays.sort(g); // 胃口
Arrays.sort(s); // 饼干尺寸
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) i++; // 满足一个孩子
j++; // 无论是否满足，都用掉这块饼干
}
return i;每次合并两个最小频率。反证法：最小的两个不合并，必定导致某种更优解可构造，矛盾。
// 用最小堆（优先队列）实现
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
for (char c : chars) pq.offer(new Node(c, freq));
while (pq.size() > 1) {
Node a = pq.poll(), b = pq.poll();
pq.offer(new Node('\0', a.freq + b.freq, a, b));
}
return pq.poll(); // 根节点本质就是贪心：每次从"未确定的点"中选距离最小的那个，之后不再更新。 （在图论章节有完整模板，此处不重复。）
会写贪心容易，证贪心难。面试常问"为什么这样是对的？"
假设存在一个最优解 O，跟贪心解 G 在第一个不同的选择上不同。 把 O 在那个点换成 G 的选择后，O' 仍然是最优解（不更差）。 重复直到 O = G。
假设贪心选择不是最优的，构造一个"交换选择后更优"的最优解，矛盾。
假设前 k 步贪心最优，证明第 k+1 步也最优。
直接用数学上的单调性证明。例：分苹果使乘积最大 → 切成 3 优先。
例子：面额 [1, 3, 4]，凑出金额 6。
| 策略 | 结果 |
|---|---|
| 贪心（每次选最大） | 4 + 1 + 1 = 3 枚 |
| 最优解 | 3 + 3 = 2 枚 ✅ |
结论：非规范币制（如 [1,3,4]）下贪心可能错，必须用 DP 保证最优。
此类问题必须用 DP（无穷背包）。
| 场景 | 错误贪心 | 正确做法 |
|---|---|---|
| 找零钱（面值不规则） | 每次选最大 | DP |
| 0/1 背包 | 按价值/重量比贪心 | DP |
| 矩阵中最长递增路径 | 局部选最大的 | DP + 记忆化 |
| 任务调度（带截止时间） | 按时长贪心 | DSU / 倒序安排 |
| 哈密顿路径 | 局部最短 | NP-hard，无多项式算法 |
一句话：贪心 = 拿一个局部最优可以"安全地"换掉任何最优解中的某些选择。