贪心
本章题海战术
贪心
面试现场口语化作答
“面试官您好，我来谈谈对贪心算法的理解和对应的高频题型。
简单说，贪心的核心就是每一步只做当下最优的选择，不回溯、不预判全局，靠每一步的局部最优堆叠出最终的全局最优解。它有三个硬性前提：问题具备最优子结构、无后效性，且满足贪心选择性质 —— 也就是局部最优能推导出全局最优。
它最大的优势是编码简洁、时空复杂度极低，大多是线性或线性对数级别的开销；但局限也很明显，适用场景很窄，一旦策略选错结果就会偏离最优解。比如经典的凑零钱问题，如果面额不是整数倍关系，贪心就会出错，这时候就得用动态规划。
接下来我可以结合 5 道面试最高频的题目，具体拆解贪心的落地思路和核心技巧。”
📌 贪心算法核心本质
- 核心思想：每步决策选取当前状态下的局部最优解，逐步推导全局最优，全程不回溯
- 必要前提：最优子结构 + 无后效性 + 贪心选择性质
- 核心优势：代码实现简单、时间复杂度低（多为 O (n)/O (nlogn)）、额外空间开销极小
- 核心局限：适用场景有限，必须严格验证策略正确性，不可盲目套用
🖼️ 贪心决策通用流程
📊 贪心 vs 动态规划 核心区别
| 对比维度 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策逻辑 | 单步选局部最优，无回溯 | 枚举所有状态，记录历史结果，支持回溯 |
| 前提条件 | 严格满足贪心选择性质 | 满足最优子结构、重叠子问题即可 |
| 时间复杂度 | 多为 O (n) / O (nlogn) | 多为 O (n²) / O (nm)，随状态数增长 |
| 空间复杂度 | 通常 O (1) 额外空间 | 需 DP 数组存储状态，O (n) / O (nm) |
| 典型场景 | 区间调度、跳跃游戏、加油站 | 背包问题、最长子序列、路径计数 |
💻 高频考题详细解题（覆盖全难度）
例题 1：LeetCode 455. 分发饼干（简单・入门必刷）
题目描述
每个孩子有对应胃口值g[i]，每块饼干有尺寸s[j]，只有饼干尺寸≥孩子胃口时才能满足。求最多能满足多少个孩子。
贪心策略推导
要最大化满足的孩子数量，应尽可能用最小的饼干满足胃口最小的孩子，把大饼干留给胃口更大的孩子，避免资源浪费。
解题步骤
- 对胃口数组、饼干数组分别升序排序
- 双指针分别指向孩子和饼干的起始位置
- 若当前饼干满足当前孩子，两个指针同时后移，计数 + 1
- 若不满足，仅饼干指针后移，尝试下一块更大的饼干
核心代码
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;
}✨ 技术亮点：排序 + 双指针线性匹配，时间复杂度 O (nlogn + mlogm)，空间复杂度 O (1)（忽略排序栈空间），是贪心思想最极简的落地实现。
例题 2：LeetCode 435. 无重叠区间（中等・区间类核心题）
题目描述
给定多个区间，求最少需要移除多少个区间，才能让剩余的区间互不重叠。
贪心策略推导
要让剩余区间最多（即移除最少），每次应选择结束时间最早的区间，给后续区间留出最多的时间空间，从而容纳更多不重叠区间。
直观示例
给定区间：[1,2]、[1,3]、[2,3]、[3,4]
最终最多保留 3 个不重叠区间，只需移除 1 个。
解题步骤
- 按区间的结束时间升序排序
- 初始化结束时间为第一个区间的结束值，不重叠计数为 1
- 遍历后续区间：若当前区间开始≥上一个结束值，说明不重叠，计数 + 1，更新结束时间
- 总区间数 - 不重叠数 = 最少移除数
核心代码
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;
}✨ 技术亮点：核心在于排序维度的选择（按结束时间而非开始时间），时间复杂度 O (nlogn)，空间 O (1)，同类题型（引爆气球、划分字母区间）均可复用该思路。
例题 3：LeetCode 45. 跳跃游戏 II（中等・大厂高频）
题目描述
非负整数数组，每个元素代表该位置可跳跃的最大长度，初始站在数组起点，求最少跳几次可以到达数组最后一个位置。
贪心策略推导
要让跳跃次数最少，每一步应在当前可达范围内，选择能跳得最远的位置作为下一步边界，最大化每一步的覆盖范围。
解题步骤
- 定义三个变量：跳跃步数
steps、当前步的右边界end、当前能到达的最远距离maxPos - 遍历数组（仅遍历到倒数第二个元素，避免终点处重复计数）
- 每次更新当前能到达的最远距离
- 当遍历到当前步的右边界时，必须跳一步，同步更新边界为当前最远距离
核心代码
public int jump(int[] nums) {
int steps = 0;
int end = 0;
int maxPos = 0;
// 关键：只遍历到倒数第二位，终点无需再跳
for (int i = 0; i < nums.length - 1; i++) {
maxPos = Math.max(maxPos, i + nums[i]);
// 走到当前边界，必须跳一步
if (i == end) {
end = maxPos;
steps++;
}
}
return steps;
}✨ 技术亮点：单次遍历完成计算，时间复杂度 O (n)，空间 O (1)；通过 “边界 + 最远位置” 双变量设计，将暴力解法的 O (n²) 优化到线性，是贪心性能优化的经典案例。
例题 4：LeetCode 134. 加油站（中等・环形贪心经典）
题目描述
环形路上有 n 个加油站，第 i 个加油站有gas[i]升汽油，从第 i 站开到第 i+1 站消耗cost[i]升汽油。判断是否存在一个起点，能绕环形路行驶一圈，返回起点下标，不存在返回 - 1。
贪心策略推导
- 全局性质：如果总油量 ≥ 总消耗，一定存在合法起点
- 局部性质：如果从起点出发，走到某站时剩余油量为负，说明起点到该站之间的所有位置都不能作为起点（中间任意点出发，到该站的剩余油量只会更少）
- 因此只需一次遍历，遇到剩余油量为负时，将起点设为下一站，重置累加和即可
解题步骤
- 定义三个变量：总剩余油量
totalSum、当前段剩余油量curSum、起点下标start - 遍历每个加油站，累加总剩余和当前剩余
- 若当前剩余小于 0，说明当前起点无效，起点设为 i+1，重置当前剩余
- 遍历结束后，若总剩余≥0 则返回起点，否则返回 - 1
核心代码
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalSum = 0;
int curSum = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
int rest = gas[i] - cost[i];
totalSum += rest;
curSum += rest;
// 当前段剩余为负，起点更新为下一站
if (curSum < 0) {
start = i + 1;
curSum = 0;
}
}
return totalSum >= 0 ? start : -1;
}✨ 技术亮点：利用环形数组的贪心性质，将暴力枚举起点的 O (n²) 复杂度优化到 O (n)，空间 O (1)，是贪心思想降低时间复杂度的典型应用。
例题 5：LeetCode 135. 分发糖果（困难・双向贪心）
题目描述
n 个孩子站成一排，每个孩子有一个评分数值。规则：评分更高的孩子必须比他相邻的孩子获得更多糖果，每个孩子至少 1 颗。求最少需要准备多少颗糖果。
贪心策略推导
相邻约束有两个方向：左边评分高→左边糖果多、右边评分高→右边糖果多。单次贪心无法同时满足两个方向，因此拆分约束，两次单向遍历：
- 从左到右遍历：保证右边评分更高的孩子，糖果数比左边多
- 从右到左遍历：保证左边评分更高的孩子，糖果数比右边多
- 每个位置取两个方向的最大值，即可同时满足双边约束，且总糖果最少
解题步骤
- 初始化糖果数组，每个孩子至少 1 颗
- 左遍历：若右边评分 > 左边评分，右边糖果 = 左边糖果 + 1
- 右遍历：若左边评分 > 右边评分，左边糖果 = max (当前值，右边糖果 + 1)
- 累加所有糖果数得到结果
核心代码
public int candy(int[] ratings) {
int n = ratings.length;
int[] candy = new int[n];
Arrays.fill(candy, 1);
// 左→右，处理右边评分更高的情况
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i-1]) {
candy[i] = candy[i-1] + 1;
}
}
// 右→左，处理左边评分更高的情况
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i+1]) {
candy[i] = Math.max(candy[i], candy[i+1] + 1);
}
}
// 求和
int sum = 0;
for (int num : candy) sum += num;
return sum;
}✨ 技术亮点：通过双向贪心拆解双向约束，将复杂的相邻依赖拆分为两个独立的单向问题，时间复杂度 O (n)，空间 O (n)，是困难题中贪心思想的经典落地。
⚠️ 技术难点与解决方案对照表
| 技术难点 | 问题描述 | 解决方案 |
|---|---|---|
| 贪心策略正确性验证 | 容易主观认为策略正确，典型反例：面额 [1,2,5,11] 凑 15 元，贪心得 4 张，全局最优仅需 3 张 | 用反证法、数学归纳法做理论验证；先尝试构造反例，存在反例直接放弃贪心；区间类优先验证「结束时间排序」 |
| 多维度排序维度选择 | 区间类问题有开始、结束两个维度，选错排序维度结果完全错误 | 调度类问题（选最多不重叠）优先按结束时间排序；覆盖类问题优先按开始时间排序；固定一个维度试错验证 |
| 环形数组贪心处理 | 加油站类环形问题，容易暴力枚举所有起点，复杂度高 | 利用全局性质（总剩余≥0 必有解）简化判断；一次遍历定位有效起点，前缀和最小值辅助验证 |
| 双向约束场景处理 | 分发糖果这类双边约束问题，单次贪心顾此失彼 | 拆分约束为两个单向规则，分别贪心处理后取交集 / 最大值；避免单次遍历同时处理两个方向 |
| 边界场景遗漏 | 空数组、单元素、刚好到达边界等场景容易计数错误 | 提前处理特殊入参；严格控制遍历边界（如跳跃游戏仅遍历到倒数第二位） |
📝 LeetCode 贪心高频考点分级清单
入门必刷（简单）
- 455.分发饼干
- 860.柠檬水找零
- 1005.K 次取反后最大化的数组和
大厂核心考点（中等）
- 55.跳跃游戏
- 45.跳跃游戏 II
- 34.加油站
- 35.无重叠区间
- 52.用最少数量的箭引爆气球
- 63.划分字母区间
- 56.合并区间
拔高困难题
- 35.分发糖果
- 316.去除重复字母
- 402.移掉 K 位数字
真实面试模拟
真实面试模拟
面试官 😊
“同学，咱们先来聊聊基础，你能用一两句话说说贪心算法到底是什么吗？它和动态规划最本质的区别在哪？”
候选人 🧑💻
“好的面试官。贪心就是每一步都选当前看起来最好的选项，希望通过局部最优累积出全局最优。它和 DP 最大的区别是：贪心不能回退，做完选择就不再改了；DP 会保存历史状态，可以在多个选择中反悔并组合出最优解。”
面试官 👍
“嗯，总结得挺到位。那我再追问一句，实际做题时，你怎么判断一个问题能不能用贪心？ 有没有一个思考框架？”
候选人
“我通常按四个步骤来：
- 分析可行性 – 看看局部最优能不能累积成全局最优；
- 设计贪心策略 – 决定按什么排序，每次选最大/最小/最早结束；
- 写出一次遍历的代码 – 维护几个关键变量；
- 快速自证 – 用一两个边界例子检验，或者用替换法简单论证。”
（面试官在白板上画了个简单流程图）
面试官
“不错，框架很清晰。那咱们上点硬菜，手写一个跳跃游戏 II 吧，返回最少跳跃次数。请写出你的 Java 代码，并解释关键变量的含义。”
候选人 🔥
“好的，这道题贪心策略是：走到当前步能到的边界就必须跳，同时用下一步能到的最远位置更新边界。”
public int jump(int[] nums) {
int steps = 0;
int curEnd = 0; // 当前步数能覆盖的最远边界
int farthest = 0; // 下一步能到达的最远位置
// 注意：不访问最后一个元素，到终点前即可
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) { // 走到边界，必须跳
steps++;
curEnd = farthest; // 边界更新为下一步最远
}
}
return steps;
}面试官 👀
“代码很干净。我问两个细节：为什么 for 循环到 len - 2 就停了？还有，怎么保证这样求出来的一定是最小步数？”
候选人
“因为当我们到达或超过最后一个位置时，游戏已经结束，不需要再跳了，所以遍历到 len - 2 可以避免在终点多跳一次。
最小步数的正确性是这样：curEnd 是当前步数下能走到的最远位置，在到达这个边界之前，我们一直在探寻下一步能到的最远 farthest；只有当不得不跳时才步数加一，并把边界扩大到 farthest。这等价于『每次都用最少的跳跃去覆盖更大的范围』，所以能得到全局最优。”
面试官 😎
“解释得很清楚。那再换一个经典题——无重叠区间。你怎么用贪心做？”
候选人
“核心贪心策略是按区间的结束时间排序，每次选一个活动，就踢掉与它重叠的，这样剩下的区间最多。”
public int eraseOverlapIntervals(int[][] intervals) {
// 按结束时间升序：贪心的灵魂
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int end = intervals[0][1];
int removeCount = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
removeCount++; // 重叠就移除
} else {
end = intervals[i][1]; // 不重叠，更新结束时间
}
}
return removeCount;
}面试官
“怎么简单证明这种『最早结束』的贪心策略是正确的？”
候选人
“可以用替换法：假设存在一个最优解，第一个区间不是最早结束的，那我们总能用那个最早结束的区间把第一个区间替换掉，因为它结束更早，不会影响后面区间的选择，而且不会使区间数量减少。所以按最早结束来贪心一定能得到最优解。”
面试官 🎯
“很好。在实际面试和刷题过程中，你会遇到哪些技术难点？怎么解决？”
候选人
“我总结了最常见的四个坑：
| 难点 | 表现 | 解决方案 |
|---|---|---|
| 找不到贪心策略 | 排序后还是纠结按什么排 | 尝试按结束时间、收益密度、身高属性排，画数轴 |
| 正确性无法保证 | 以为能贪心，提交全 WA | 手写 2~3 个边界测例，用反证法/替换法快速自证 |
| 与 DP 混淆 | 把需要回退的题当贪心做 | 看题目是否要求『最多/最少/最长/最短』且有后效性，优先想 DP |
| Java 实现细节 | 数组排序、比较器、边界处理 | 熟练 Comparator，善用 Integer.compare 防溢出 |
"贪心从来不是猜，而是基于排序和前瞻变量的确定性策略。"
面试官 😊
“这次我们直接多上几道真题，看看你如何用贪心思路拆解。先从最简单的热身开始——分发饼干（LeetCode 455）。说说思路和代码。”
候选人 🧑💻
“这题是贪心入门。孩子和饼干都排序，然后用双指针，用最小的饼干去满足胃口最小的孩子，能吃饱就两个指针都动，否则只移动饼干指针找更大的饼干。”
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; // 满足的孩子数
}💡 关键点：排序 O(nlogn)，双指针 O(n)，整体 O(nlogn)。贪心策略——用最小的代价满足最小的需求。
面试官 👍
“好，那进阶一点，跳跃游戏 I（LeetCode 55），不是求最小步数，而是问能不能到终点。这个怎么贪心？”
候选人
“更简单，我们只维护一个最远可达位置 maxReach，遍历时不断更新它，如果当前位置大于 maxReach 说明卡死，返回 false；如果 maxReach 提前覆盖终点，直接返回 true。”
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]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}面试官 👀
“那 加油站（LeetCode 134） 这道题呢？很多人卡在暴力模拟，贪心怎么一次遍历出结果？”
候选人
“这题的贪心逻辑很巧妙：先算总油量差，总剩余 >=0 才有解。然后维护当前油箱余量，一旦油箱变负，说明从起点到当前位置都不可能是合法起点，直接将下一站设为新起点，并清空油箱。最后剩下的起点就是答案。”
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalTank = 0; // 总剩余，判断全局是否有解
int curTank = 0; // 当前油箱剩余
int start = 0; // 候选起点
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
totalTank += diff;
curTank += diff;
if (curTank < 0) { // 油箱见底，重置起点
start = i + 1;
curTank = 0;
}
}
return totalTank >= 0 ? start : -1;
}💡 贪心证明：如果从 A 到 B 的途中油量变负，那么 A～B 之间的任何站作为起点，走到 B 时油量都会更差，所以可以直接跳过这一段。这是局部失效直接丢弃的贪心思想。
面试官 🔥
“不错，逻辑讲得很透。再上道二维贪心——根据身高重建队列（LeetCode 406），这题怎么思考？”
候选人
“这题需要两次贪心：先按身高降序排，同身高按 k 值升序排；然后依次把人插入到队列第 k 个位置，因为高个子先站位，矮个子后插入不会影响高个子的相对顺序。”
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];
});
List<int[]> res = new ArrayList<>();
for (int[] p : people) {
res.add(p[1], p); // 直接插到第 k 个位置
}
return res.toArray(new int[people.length][2]);
}🧠 为什么这样是对的？
高个子先插入时，前面只有比他还高的人，所以 k 值就是当前需要插入的位置。后面插入的矮个子无论放哪，都不会影响高个子的 k 值正确性。这就是按顺序构造的贪心策略。
面试官 😎
“如果有一道题看起来也能贪心，但实际需要 DP，你怎么快速辨别？你有没有踩过坑？”
候选人
“踩过，比如背包问题。很多人觉得按单位价值贪心即可，但 0-1 背包有容量限制，局部最优会错过全局组合。我的判断方法：
- 如果问题有无后效性，且局部最优堆叠起来就是全局，那贪心；
- 如果当前选择会影响后面选项的可能性空间（例如容量、剩余步数），且需要穷举组合，就必须 DP 或回溯。”
面试官 💬
“总结得很好。这些典型题的难点和对应解决思路，你能整理一下吗？”
候选人
“当然，我列个表，经常出现的四类难点及对策：
| 题型 | 难点 | 解决方案 |
|---|---|---|
| 区间调度 | 为什么按结束时间排序最优？ | 用替换法想象第一个区间换成最早结束的，不减少后续机会 |
| 跳跃游戏 | 步数统计边界处理 | 明确 curEnd 和 farthest，只在触达边界时步数+1 |
| 加油站/贪心重置 | 为什么失败后直接跳过中间部分？ | 证明中间任何点为起点都更差，一次遍历重置起点 |
| 二维贪心 | 排序规则怎么定？ | 先确定一个维度（如身高），再确定另一个（k 值），用插入顺序体现贪心 |
面试官 🎯
“最后，我把贪心高频必刷的题单再贴一下，你把刚才讨论的几道题重点复盘，面试绝对够用。”
| 题号 | 题目 | 难度 | 贪心核心 | 说明 |
|---|---|---|---|---|
| 455 | 分发饼干 | 🟢 | 排序+双指针 | 最小满足最小 |
| 121 | 买卖股票 | 🟢 | 维护历史最低价 | 本质贪心 |
| 55 | 跳跃游戏 | 🟡 | 维护最远可达 | 可行性判断 |
| 45 | 跳跃游戏 II | 🟡 | 边界触发跳跃 | 步数最小化 |
| 435 | 无重叠区间 | 🟡 | 按结束时间排序 | 区间调度模板 |
| 452 | 气球问题 | 🟡 | 重叠区间合并 | 与 435 同源 |
| 406 | 身高重建队列 | 🟡 | 降序+按 k 插入 | 二维贪心 |
| 621 | 任务调度器 | 🟡 | 最大频率公式 | 冷却期安排 |
| 134 | 加油站 | 🟡 | 总剩余+局部重置 | 连续和判定 |
面试官 🚀
“记住，面试中贪心题重思路论证、轻代码堆砌。把上述题目的贪心证明理由和一次遍历代码烂熟于心，再配合复杂度分析，就能让面试官感觉你基本功扎实。今天的模拟就到这，回去多敲几遍代码，加油 😎👍。”