给定一组活动，每个活动都有开始时间和结束时间，要求选出最多的互不重叠的活动。最直观的思路是尝试所有可能的组合，但这样的时间复杂度是指数级的。如果换一个角度：每次都选择结束时间最早且不与已选活动重叠的活动，只需要一次遍历就能得到最优解。
这就是贪心算法的核心魅力：在每一步做出当前看起来最好的选择，无需回溯，却能保证最终结果的正确性。这种"短视"的策略为什么能奏效？答案隐藏在问题本身的特殊结构中。
贪心算法的本质：当局部最优恰好导向全局最优
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法策略。与动态规划不同，贪心算法不保存之前的计算结果，也不进行回溯——一旦做出选择，就不再改变。
贪心算法能够成功的核心在于两个关键性质：
贪心选择性质（Greedy Choice Property）：通过做出局部最优选择，能够得到全局最优解。这意味着在选择时不需要考虑子问题的解，只需要做出当前最好的选择即可。
最优子结构（Optimal Substructure）：问题的最优解包含子问题的最优解。当我们做出一个贪心选择后，原问题就变成了一个规模更小的子问题。
这两个性质听起来相似，但有着本质区别。贪心选择性质说的是"可以用贪心方法做选择"，而最优子结构说的是"做出选择后剩余部分的解法仍然是最优的"。正是因为这两个性质的同时成立，才使得贪心算法能够成功。
拟阵理论：贪心算法的数学基石
1971年，数学家 Jack Edmonds 在论文《Matroids and the Greedy Algorithm》中建立了贪心算法与拟阵（Matroid）理论之间的联系。拟阵是一个抽象的代数结构，满足两个核心公理：
遗传性（Hereditary Property）：如果一个集合是独立的，那么它的所有子集也是独立的。
交换性（Exchange Property）：如果集合 $A$ 和 $B$ 都是独立的，且 $|A| < |B|$，那么存在元素 $x \in B \setminus A$，使得 $A \cup \{x\}$ 也是独立的。
对于一个加权拟阵，如果权重函数 $w$ 将每个元素映射到一个正实数权重，那么贪心算法可以找到最大权重的独立集：按权重降序排列元素，依次将元素加入结果集，只要加入后仍然保持独立性。
这个定理告诉我们：当一个问题可以被建模为拟阵上的优化问题时，贪心算法一定能找到最优解。最小生成树的 Kruskal 算法和 Prim 算法正是这一理论的经典应用。
证明贪心算法正确性的两种方法
判断一个贪心算法是否正确，通常需要严格的数学证明。两种最常用的证明方法是"贪心保持领先"（Greedy Stays Ahead）和"交换论证"（Exchange Argument）。
贪心保持领先
这种方法的核心思想是：证明在算法执行的每一步，贪心解都"不差于"任何其他解。通过归纳法，可以推导出最终贪心解也是最优的。
以活动选择问题为例，按结束时间排序后，贪心算法选择的活动总是比任何其他算法选择的活动更早结束。这给后续选择留出了更多空间，因此贪心解不可能比最优解差。
交换论证
交换论证的思路是：从一个假设的最优解出发，逐步将其转换为贪心解，同时证明每一步转换都不会使解的质量下降。
假设存在一个最优解 $O$ 与贪心解 $G$ 不同。找到第一个分歧点，证明可以将 $O$ 中的选择替换为 $G$ 中的对应选择，而不会破坏最优性。重复这个过程，最终可以将 $O$ 转换为 $G$，从而证明 $G$ 也是最优解。
这两种方法各有适用场景。当贪心解的结构比较规则时，贪心保持领先更直观；当需要比较两个解的差异时，交换论证更为有效。
LeetCode 贪心算法题目的六大类型
LeetCode 中涉及贪心算法的题目可以归纳为六大类型，每类问题都有其独特的解题模式和关键洞察。
类型一：区间调度问题
区间调度问题是贪心算法最经典的应用领域。这类问题的核心是处理时间区间的重叠关系。
LeetCode 435. 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
// 按结束时间排序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 1; // 保留的区间数
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
// 不重叠，保留该区间
count++;
end = intervals[i][1];
}
// 重叠则跳过（相当于移除）
}
return intervals.length - count;
}
关键洞察：按结束时间排序后，每次选择结束最早且不重叠的区间。结束最早的区间给后续选择留出最多的空间。
LeetCode 452. 用最少数量的箭引爆气球
在二维空间中有许多球形气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。一支弓箭可以沿着 x 轴垂直射出，如果一支箭射出的坐标是 x，且满足 start ≤ x ≤ end，则该气球会被引爆。
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
// 按结束坐标排序（注意使用减法可能导致溢出）
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] > end) {
// 需要新的一支箭
arrows++;
end = points[i][1];
}
// 否则当前箭可以继续射穿这个气球
}
return arrows;
}
这两个问题本质相同：在区间集合中找最多的不重叠区间。活动选择问题的贪心策略具有普适性。
类型二：跳跃与可达性问题
这类问题涉及在数组中"跳跃"，判断能否到达终点或计算最少跳跃次数。
LeetCode 55. 跳跃游戏
给定一个非负整数数组，初始位于数组第一个位置，数组中每个元素代表在该位置可以跳跃的最大长度，判断能否到达最后一个位置。
public boolean canJump(int[] nums) {
int maxReach = 0; // 当前能到达的最远位置
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) {
// 无法到达当前位置
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
关键洞察：不需要记录每个位置的具体跳跃路径，只需维护一个变量表示当前能到达的最远位置。如果在某位置发现无法到达，则直接返回失败。
LeetCode 45. 跳跃游戏 II
计算到达最后一个位置的最少跳跃次数。
public int jump(int[] nums) {
int jumps = 0; // 跳跃次数
int currentEnd = 0; // 当前跳跃能到达的边界
int farthest = 0; // 下一次跳跃能到达的最远位置
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
// 到达边界，必须跳跃
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
LeetCode 134. 加油站
在一条环路上有 n 个加油站，第 i 个加油站有汽油 gas[i] 升。从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。从其中一个加油站出发，判断能否绕环路行驶一周。
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;
int currentGas = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
totalGas += gas[i] - cost[i];
currentGas += gas[i] - cost[i];
if (currentGas < 0) {
// 从当前起点无法到达 i+1，换下一个起点
start = i + 1;
currentGas = 0;
}
}
return totalGas >= 0 ? start : -1;
}
关键洞察：如果从加油站 A 出发无法到达加油站 B，那么从 A 到 B 之间的任何加油站出发都无法到达 B。因此可以直接将起点设为 B。
类型三：资源分配问题
这类问题涉及将有限资源分配给多个对象，使得满足某些约束条件的同时优化目标。
LeetCode 135. 分发糖果
n 个孩子站成一排。给孩子评分，每个孩子至少分配 1 个糖果，评分更高的孩子必须比相邻孩子得到更多糖果。求最少需要多少糖果。
public int candy(int[] ratings) {
int n = ratings.length;
int[] leftToRight = new int[n];
int[] rightToLeft = new int[n];
// 初始化：每个孩子至少 1 颗糖果
Arrays.fill(leftToRight, 1);
Arrays.fill(rightToLeft, 1);
// 从左到右：如果比左边评分高，糖果比左边多
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
leftToRight[i] = leftToRight[i - 1] + 1;
}
}
// 从右到左：如果比右边评分高，糖果比右边多
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
rightToLeft[i] = rightToLeft[i + 1] + 1;
}
}
// 取两个方向的较大值，满足两个约束
int total = 0;
for (int i = 0; i < n; i++) {
total += Math.max(leftToRight[i], rightToLeft[i]);
}
return total;
}
关键洞察：每个孩子受左右两个邻居的影响。单次遍历无法同时处理两个方向的依赖，因此需要两次遍历分别处理，最后取较大值。
LeetCode 455. 分发饼干
每个孩子都有一个胃口值 g[i]，每块饼干有一个尺寸 s[j]。只有当 s[j] ≥ g[i] 时孩子才能满足。求最多能满足多少孩子。
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g); // 孩子胃口排序
Arrays.sort(s); // 饼干尺寸排序
int child = 0, cookie = 0;
while (child < g.length && cookie < s.length) {
if (s[cookie] >= g[child]) {
// 这块饼干能满足这个孩子
child++;
}
cookie++; // 无论是否满足，这块饼干都被"使用"了
}
return child;
}
关键洞察：用最小的满足条件的饼干去满足胃口最小的孩子。这是典型的贪心匹配策略。
类型四：重排构造问题
这类问题要求将给定的元素重新排列，使其满足特定条件或达到某种最优。
LeetCode 406. 根据身高重建队列
假设有打乱顺序的一群人站成一排。每个人由一个二元组 (h, k) 表示，h 是身高，k 是排在这个人前面且身高大于等于 h 的人数。重建队列。
public int[][] reconstructQueue(int[][] people) {
// 按身高降序排列，身高相同时按 k 升序排列
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) {
return b[0] - a[0]; // 身高降序
}
return a[1] - b[1]; // k 升序
});
List<int[]> result = new ArrayList<>();
for (int[] person : people) {
// 在指定位置插入
result.add(person[1], person);
}
return result.toArray(new int[people.length][]);
}
关键洞察：先处理高个子，因为高个子的位置不受矮个子影响。每次插入时，之前已插入的人都比当前人高或相等，因此可以直接按 k 值插入。
LeetCode 767. 重构字符串
给定一个字符串 S，检查是否能重新排列其中的字母，使得相邻的字母都不相同。
public String reorganizeString(String s) {
int[] count = new int[26];
int maxCount = 0;
for (char c : s.toCharArray()) {
count[c - 'a']++;
maxCount = Math.max(maxCount, count[c - 'a']);
}
// 如果某个字符超过一半，无法重构
if (maxCount > (s.length() + 1) / 2) {
return "";
}
char[] result = new char[s.length()];
int index = 0;
// 先填充偶数位置，再填充奇数位置
for (int i = 0; i < 26; i++) {
while (count[i] > 0) {
result[index] = (char) ('a' + i);
count[i]--;
index += 2;
if (index >= s.length()) {
index = 1; // 切换到奇数位置
}
}
}
return new String(result);
}
关键洞察：将出现次数最多的字符放在偶数位置（0, 2, 4, …），剩余字符填入空位。这样最大程度地将相同字符隔开。
LeetCode 179. 最大数
给定一组非负整数，重新排列每个数的顺序使之组成一个最大的整数。
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
// 自定义排序：比较两种拼接顺序
Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
// 处理前导零
if (strs[0].equals("0")) {
return "0";
}
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str);
}
return sb.toString();
}
关键洞察：对于两个数 a 和 b，如果拼接 ab > ba，则 a 应该排在 b 前面。这个比较关系具有传递性（需要证明），因此可以直接排序。
类型五：序列分割问题
这类问题要求将序列划分为若干段，满足特定条件。
LeetCode 763. 划分字母区间
字符串 S 由小写字母组成。将字符串划分为尽可能多的片段，使得每个字母最多只出现在一个片段中。
public List<Integer> partitionLabels(String s) {
// 记录每个字符最后出现的位置
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> result = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 扩展当前片段的边界
end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) {
// 到达片段边界，可以划分
result.add(end - start + 1);
start = i + 1;
}
}
return result;
}
关键洞察：一个片段的边界必须包含其中所有字符的最后一次出现。遍历时动态扩展边界，直到当前位置等于边界。
LeetCode 376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。求最长摆动子序列的长度。
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
关键洞察：不需要记录具体序列，只需要知道以当前结尾的最长摆动序列长度。贪心地选择局部极值点即可。
类型六：调度优化问题
这类问题涉及任务调度、时间安排等。
LeetCode 621. 任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以按任意顺序执行，每个任务执行时间为 1 个单位时间。在任何一个单位时间，CPU 可以完成一个任务，或者处于待机状态。两个相同种类的任务之间必须有长度为 n 的冷却时间，求完成所有任务的最短时间。
public int leastInterval(char[] tasks, int n) {
int[] count = new int[26];
int maxFreq = 0;
for (char task : tasks) {
count[task - 'A']++;
maxFreq = Math.max(maxFreq, count[task - 'A']);
}
// 统计有多少种任务出现了最大次数
int maxCount = 0;
for (int c : count) {
if (c == maxFreq) {
maxCount++;
}
}
// 公式推导：(maxFreq - 1) * (n + 1) + maxCount
// 但还需要考虑任务总数
return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
}
关键洞察：出现次数最多的任务决定了调度的框架。假设任务 A 出现 $x$ 次，需要 $x-1$ 个完整的"冷却周期"，每个周期长度为 $n+1$。最后加上所有出现 $x$ 次的任务。如果任务种类足够多，可以填满所有冷却间隙，答案就是任务总数。
贪心算法的模式识别
通过上述题目分析，可以总结出贪心算法的常见模式：
排序后贪心：很多贪心问题需要先按某种规则排序，然后按序处理。排序规则往往是解题的关键。区间问题按结束时间排序，匹配问题按大小排序，构造问题按特定条件排序。
双指针配合：排序后常配合双指针实现线性扫描。左指针、右指针分别从头尾向中间移动，或两个指针分别遍历两个序列。
正向反向遍历：当某个位置的状态受两边邻居影响时，需要分别从左到右和从右到左遍历。如分发糖果问题。
维护极值变量：很多问题只需要维护一个或几个极值变量，而不需要完整记录所有信息。如跳跃游戏中的最远可达位置。
数学公式推导：某些问题的答案可以直接由数学公式计算。如任务调度器问题。
贪心与动态规划的边界
贪心算法和动态规划都用于求解优化问题，都要求问题具有最优子结构。关键区别在于贪心选择性质。
如果问题具有贪心选择性质，那么贪心算法通常比动态规划更高效——贪心算法是自顶向下的一次扫描，而动态规划通常需要自底向上计算所有子问题。
当不确定问题是否具有贪心选择性质时，可以先尝试举反例。如果能找到反例证明贪心策略失败，则需要改用动态规划。典型的例子是 0-1 背包问题：贪心地选择单位价值最高的物品不一定得到最优解。
总结
贪心算法的魅力在于其简洁性——每一步只做当前最优的选择，却能得到全局最优解。这种简洁性的背后是问题本身的特殊结构：贪心选择性质和最优子结构。理解这两种性质，掌握交换论证和贪心保持领先两种证明方法，是运用贪心算法解决问题的关键。
在 LeetCode 中，贪心算法的题目主要集中在区间调度、跳跃覆盖、资源分配、重排构造、序列分割和调度优化六大类型。每种类型都有其独特的解题模式，但核心思想都是找到合适的"贪心策略"——即在每一步应该做出什么样的局部最优选择。
最后需要记住：贪心算法不是万能的。在不确定问题是否适合贪心时，优先考虑动态规划，或者通过举反例验证贪心策略的正确性。算法选择本身就是一个需要权衡的过程。
参考资料：
- Cormen, T. H., et al. “Introduction to Algorithms, Chapter 16: Greedy Algorithms.” MIT Press.
- Edmonds, J. (1971). “Matroids and the Greedy Algorithm.” Mathematical Programming, 1(1), 127-136.
- Kleinberg, J., & Tardos, E. “Algorithm Design, Chapter 4: Greedy Algorithms.” Pearson.
- GeeksforGeeks. “Greedy Algorithms.” https://www.geeksforgeeks.org/dsa/greedy-algorithms/
- LeetCode Discuss. “Master Greedy Problems List.” https://leetcode.com/discuss/post/7487082/