1. 贪心算法：从直觉到严谨的跨越
刷题刷到第28天，很多人会被贪心算法（Greedy Algorithm）这个名字误导，觉得“贪心”就是目光短浅、只顾眼前。实际并非如此。贪心算法每次确实只做局部最优选择，但厉害之处在于，在特定结构的问题里，这些局部最优会自然收敛为全局最优。它不回溯、不重算、不纠结历史状态，只要走对路子，一把梭到底。
这篇文章适合三类人：一是算法刚入门、想系统整理贪心题型的同学；二是面试前需要快速回顾高频贪心场景的开发者；三是在实际工程中处理调度、区间合并、资源分配问题时，想找简洁方案的人。我会从核心思想、典型题型、踩坑经验三个维度展开，帮你把贪心算法真正用起来。
先明确一个基本认知：贪心不是一种算法模板，而是一种解题策略。它要求你对问题结构有足够深的洞察，能判断“局部最优能推出全局最优”。这个判断能力，刷题就是最直接的训练方式。
2. 贪心算法的核心思想与使用前提
2.1 贪心的本质：局部最优与全局最优的关系
贪心每一步都在当前状态下选出“看起来最好”的选项，然后进入下一步，不会因为后面发生变化而回头调整。这里面隐含了一个关键假设：问题的全局最优解，可以由一系列局部最优解组合而成。
这个假设不是天然成立的。举个反例：背包问题里，如果每件物品可以拆分（分数背包），按单位价值从大到小拿就是贪心正解。但如果物品不可拆分（0-1背包），按单位价值贪心很可能不是最优，因为贪心会留下无法填满的缝隙，动态规划才能处理这种需要统筹全局的情况。
所以使用贪心的第一步，就是验证问题是否满足贪心选择性质。常用做法是枚举几组特殊数据自己去测，或者尝试构造反例。如果某个贪心策略在面对反例时失效，就要换思路了。
2.2 贪心与动态规划的根本区别
贪心和动态规划很容易混淆，因为它们都用于解决最优化问题。区别在于：
- 贪心：每个阶段做一次选择，选完就固定，依赖“当前最优”。
- 动态规划：枚举所有可能的转移，通过比较保留最优子结构的结果，依赖“全局比较”。
用一个生活化类比：贪心像去菜市场买菜，只看眼前哪个摊位价格低就买哪个，买完就走；动态规划像做月度预算，要把每一天的开销、冰箱剩余、未来价格波动都放在一起综合考虑，最终找到整体最优方案。
在代码实现层面，贪心通常就是排序加一次遍历，动态规划则需要维护状态数组或者做记忆化搜索。因此能贪心解决的问题，代码往往非常短，这也是贪心被称作“代码短、思维难”的原因。
2.3 两个关键性质：贪心选择性与最优子结构
严格来说，贪心算法的正确性依赖两个性质：
- 贪心选择性：每一步的局部最优选择，最终可以被包含在全局最优解中。
- 最优子结构：一个问题的最优解包含其子问题的最优解。
这两个性质听起来数学味很浓，实际做题时我的验证方法是：先凭直觉写出一版贪心策略，然后立刻构造几组刁钻数据测试，尤其是边界数据和极端数据。如果能过，再尝试从数学上简单说明为什么局部选择不会影响后续的全局最优。
注意，“通过几组测试用例”不是正确性证明，只能说明你的策略暂时没被推翻。考试和面试中，如果时间紧张，这种验证方式比较实用；但实际项目中若有严谨性要求，还是要多花时间做逻辑推导。
2.4 用数学归纳法验证贪心正确性的思路
数学归纳法在贪心证明中很常用。思路是：
- 证明第一步贪心选择正确，即存在一个最优解包含这个贪心选择。
- 证明选择后，剩余子问题是同类问题，且最优解包含该子问题的最优解。
以活动选择问题为例：按结束时间最早选择活动，先证明存在最优解包含最早结束的活动，然后删掉该活动后，剩余活动选择又是相同结构的问题，归纳成立。
实际做题时，我不一定会写完整证明，但这个思路能帮助我判断一个贪心策略是否靠谱。遇到拿不准的题目，先套这个逻辑想想，比盲目提交试错要高效得多。
3. 高频经典题型拆解：从简单到进阶
3.1 分发饼干：理解排序匹配的基本模型
这是贪心入门的第一道题，问题描述是：有一群孩子和一堆饼干，每个孩子有一个胃口值，每块饼干有一个尺寸值，只有饼干尺寸大于等于孩子胃口时孩子才能吃饱，问最多能喂饱几个孩子。
标准做法是两个数组都排序，然后用小饼干满足小胃口，依次匹配。核心逻辑是：最小尺寸的饼干先尝试喂给胃口最小的孩子，如果满足不了，这块饼干对于更大的胃口也一定没用，直接丢掉。
def findContentChildren(g, s): g.sort() s.sort() i = j = 0 while i < len(g) and j < len(s): if s[j] >= g[i]: i += 1 j += 1 return i这个代码里藏着贪心的两个关键思想：排序（让选择有序化）和丢弃（无法满足当前最小需求的选择直接淘汰，无需回头）。面试时遇到这题的变体——比如每个孩子可以拿多块饼干、或者饼干可以拼接——核心仍然是排序加双指针，只是匹配规则变了。
3.2 摆动序列：状态机里的贪心选择
摆动序列要求相邻数字之间的差严格正负交替，问从原序列中删掉最少的元素，使得剩余序列成为摆动序列。这道题表面上像动态规划，但实际上贪心做得更干净。
关键洞察是：上下摆动的转折点是必须保留的，而连续上升或下降区间的中间点都可以删掉。因此只需要统计序列中的“峰”和“谷”的个数。
def wiggleMaxLength(nums): if len(nums) < 2: return len(nums) prediff = nums[1] - nums[0] count = 2 if prediff != 0 else 1 for i in range(2, len(nums)): diff = nums[i] - nums[i-1] if (diff > 0 and prediff <= 0) or (diff < 0 and prediff >= 0): count += 1 prediff = diff return count这里的贪心策略可以理解为：当趋势发生变化时保留转折点，趋势不变时忽略。实际写代码时，我因为prediff初始化和等号处理踩过不少坑。注意判断条件里的等于号很重要——它处理的是序列首尾出现平坡的情况，少了等号结果会错误。
3.3 跳跃游戏：从可达性到最少步数
跳跃游戏有两个版本。版本一问能不能到达最后一个下标，版本二问最少跳几次。两者都适合用贪心处理，但思路有差异。
版本一的贪心思路是维护一个当前能达到的最远位置max_reach，遍历每个下标，如果i > max_reach说明到不了这里，直接返回False，否则更新max_reach = max(max_reach, i + nums[i])。
def canJump(nums): max_reach = 0 for i, jump in enumerate(nums): if i > max_reach: return False max_reach = max(max_reach, i + jump) return True版本二问最少步数，需要额外维护两个变量：当前一步能达到的边界end和下一步能达到的最远位置farthest。遍历时不断更新farthest，当走到end时，步数加一，把end更新为farthest。
这两个版本我觉得是贪心算法最好的入门练习，因为它们几乎不需要复杂数据结构，但对“局部最优如何反映全局”的理解要求很高。面试中非常常见，值得多做几遍。
3.4 加油站：环路上的全局能量守恒
加油站问题的描述是：一条环形路上有若干加油站，每个站能加的油量和到下一站消耗的油量已知，问能否从某个站出发跑完一圈，返回起始站编号。
常见的贪心解法是：从起点开始累计剩余油量total和当前油量cur，一旦cur变成负数，说明从当前起点到这段路的任何一个站都不可能作为起点，直接把起点重置为下一站，cur清零。
def canCompleteCircuit(gas, cost): total, cur, start = 0, 0, 0 for i in range(len(gas)): total += gas[i] - cost[i] cur += gas[i] - cost[i] if cur < 0: start = i + 1 cur = 0 return start if total >= 0 else -1这个解法的精妙之处在于全局判据：总加油量小于总消耗量时一定无解；否则一定存在唯一起点，且用上述贪心规则可以找到。我第一次做这题时试图枚举所有起点，复杂度是O(n²)，后来才意识到这个题目考察的就是对环路结构的理解，而不是暴力枚举。
3.5 柠檬水找零：优先消耗大面额钞票的自律
柠檬水找零问题是典型的模拟类贪心：顾客可能用5美元、10美元、20美元买一杯5美元的柠檬水，问你是否能始终正确找零。
贪心策略很直观：收到20美元时，找零优先使用10美元加5美元的组合，实在没有10美元才用三张5美元。因为5美元是最灵活的找零面额，要尽量保留。
def lemonadeChange(bills): five = ten = 0 for bill in bills: if bill == 5: five += 1 elif bill == 10: if not five: return False five -= 1 ten += 1 else: if ten and five: ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return True这道题的教训是：贪心策略有时候不是“选最多”，而是“选最不浪费的”。优先花掉10美元，是因为它在找零场景中功能受限，而5美元是万能牌。
3.6 重叠区间类问题：排序与贪心的经典组合
重叠区间问题是贪心算法应用最广泛的场景，常见变体包括：无重叠区间、用最少数量的箭引爆气球、合并区间、划分字母区间。
以无重叠区间为例：给定一系列区间，求移除最少区间使剩余区间互不重叠。经典解法是按区间结束时间排序，然后贪心地保留结束时间最早的区间，因为结束时间越早，留给后面的空间越大。
def eraseOverlapIntervals(intervals): intervals.sort(key=lambda x: x[1]) end = float('-inf') count = 0 for s, e in intervals: if s >= end: end = e else: count += 1 return count为什么按结束时间排序而不是按开始时间排序？这是这道题最容易踩的坑。按开始时间排序容易陷入“开始得早但结束得晚”的陷阱，会白白牺牲后续很多区间；按结束时间排序则天然保证了“每次选择都给未来留最大余地”。这些细节才是真正拉开算法水平差距的地方。
4. 实战进阶：复杂贪心的思考框架
4.1 单调递增的数字：从右往左修正的贪心
给定一个非负整数N，找到小于等于N的最大整数，且这个数的各位数字单调递增，代码实现很精简，但思考过程很考验对数字结构的理解。
暴力法是从N往下逐个枚举，直到找到单调递增的数字，复杂度O(N * len(N))，数字一大就废了。贪心解法是：从左到右扫描数字，找到第一个违反递增关系的位，把这一位减一，后面所有位变成9。
def monotoneIncreasingDigits(N): s = list(str(N)) n = len(s) pos = n for i in range(n-1, 0, -1): if s[i] < s[i-1]: pos = i s[i-1] = str(int(s[i-1]) - 1) for i in range(pos, n): s[i] = '9' return int(''.join(s))这里有一个细节：为什么要从右往左扫描？因为修改前面的数字可能导致前面的递增关系也被破坏，需要逐级向前修正。从右往左遍历，可以一遍完成所有修正，不需要重复扫描。这种“反向扫描加连锁修正”的模式，在很多数字相关的贪心题目中都有体现。
4.2 监控二叉树：树形结构上的贪心选择
监控二叉树是贪心算法中比较难的题目：给定一棵二叉树，在节点上安装摄像头可以监控自己、父节点和子节点，求覆盖整棵树所需的最少摄像头数量。
这道题的贪心策略是：从叶子节点的父节点开始安装摄像头，自底向上覆盖。每个节点有三种状态：被覆盖但不安装、安装了摄像头、未被覆盖。通过后序遍历，节点根据子节点状态决定自己的状态。
def minCameraCover(root): res = 0 def dfs(node): nonlocal res if not node: return 1 left = dfs(node.left) right = dfs(node.right) if left == 0 or right == 0: res += 1 return 2 if left == 2 or right == 2: return 0 return 1 if dfs(root) == 0: res += 1 return res这道题展示了贪心在树结构上的应用：局部最优选择是尽可能让摄像头的覆盖范围最大化，而叶子节点的父节点就是性价比最高的安装点。代码本身不难，难点在于状态定义和自底向上的顺序。建议反复练习，直到能独立推导出三种状态的逻辑。
4.3 按要求补齐数组：贪心覆盖范围的数学推导
给定一个已排序的正整数数组nums和一个目标值n，要求向数组中补充最少数量的数字，使得区间[1, n]内所有数字都能被数组中的若干数字表示（每个数字只能使用一次）。返回最少补充数量。
这道题的贪心思路是：维护当前可以覆盖的范围[0, range_end)，遍历数组。如果下一个数nums[i] <= range_end，则扩展范围为range_end + nums[i]；否则需要补充一个数字range_end，让范围翻倍。
def minPatches(nums, n): cur = 1 i = 0 count = 0 while cur <= n: if i < len(nums) and nums[i] <= cur: cur += nums[i] i += 1 else: cur *= 2 count += 1 return count这个题的关键证明是：如果当前能覆盖[0, x)，加入一个不大于x的数字，覆盖范围一定延伸到[0, x + nums[i])；如果下一个数字大于x，则必须引入x本身，因为x是当前无法表示的最小数，而引入x能让范围翻倍。整个过程是“缺什么补什么”的贪心思路，每一步补充都是必需且最低成本的。
这道题目在面试中较少出现，但它对贪心思想的理解深度要求很高，如果能把这道题讲清楚，说明你真的懂了贪心的“范围覆盖”模型。
5. 贪心算法在真实场景中的应用与延伸
5.1 任务调度与资源分配
贪心算法在任务调度中非常常见。比如操作系统中的短作业优先调度，就是典型的贪心：每次选择执行时间最短的任务，能有效降低平均等待时间。再比如项目管理中的关键路径资源分配，虽然不是纯粹的贪心就能解决，但很多启发式算法都借鉴了贪心思想作为初始解生成器。
实际做后端服务时，我经常遇到“一批请求需要分配处理线程”的场景。如果线程资源有限，按处理时间从短到长执行，确实是降低平均响应时间的一个有效策略。这和算法题里的排序加贪心本质上是同一套思路。
5.2 哈夫曼编码与数据压缩
哈夫曼编码是贪心算法的经典教学案例：根据字符出现频率构造最优前缀编码，每次从频率最小的两个节点合并出新节点，重复直到生成一棵树。这个过程中每一步都是局部最优——合并当前频率最低的两个——但在全局上恰恰能构造出带权路径长度最小的二叉树。
我在实际项目中处理过日志数据的压缩需求。虽然大多数情况下直接用现成压缩库，但理解哈夫曼编码的原理，对合理设计数据结构、判断压缩率瓶颈很有帮助。尤其是当你需要为特定格式的定制数据做压缩时，哈夫曼思想可以快速给出一个性能可接受的方案。
5.3 网络路由与图论中的贪心
Dijkstra最短路径算法和Prim最小生成树算法，本质上都是贪心思想在图上应用的典范。Dijkstra每次从未处理节点中选择距离起点最近的节点，Prim每次选择连接已选集合和未选集合的最小权重边。这两个算法都用到了“当前最优扩展”的思路。
图论中的贪心算法价值在于：它提供了高效且容易实现的近似解或精确解。尤其是在动态网络、稀疏图这样的场景中，贪心算法的低时间复杂度和易维护性，让它成为工程实现的首选。
不过也要注意，图的有些问题上贪心并不能得到最优解，比如旅行商问题。这时候就需要退而求其次，用贪心生成一条初始路径，再配合局部搜索算法做迭代优化。这种“贪心加启发式”的组合拳，在工业界的路径规划、物流调度中非常普遍。
6. 刷题常见误区与实战心得
6.1 盲目套用贪心模板，忽视反例验证
我发现很多同学（包括我自己早期）的问题在于：拿到题目以后，凭直觉写一个贪心策略，不构造反例就提交。实际上无论题目看起来多简单，都应该先构造几个极端用例。比如全零数组、全相等数组、递增序列、递减序列、只有一个元素、两个元素相同等边界情况。
特别是排序相关的贪心题，一定要想清楚排序的键是什么。比如区间问题，到底是按左端点排序还是右端点排序，这决定了整个贪心策略的正确性。一个稳妥的做法是：写代码之前，先花两分钟在纸上画几条区间线，模拟一下排序后的匹配过程，确认没有反例再动手指码。
6.2 忽略数据的类型范围和溢出问题
贪心算法里经常涉及累加、比较大小。比如加油站问题中计算总剩余油量，如果数据范围很大，用整型累加可能溢出。Python虽然不容易溢出，但其他语言如Java、C++就要特别小心。即使在Python中，也要注意性能问题——超大数组上的多次排序和重复遍历会拖慢程序。
解决思路是：先看数据范围的约束条件，评估时间复杂度和空间复杂度是否可行。很多贪心题目对时间复杂度要求是O(n log n)，对应排序加一次遍历。如果多一层嵌套循环，就要考虑是不是做法的思路出了问题。
6.3 用反证法快速检验贪心策略
面试时可以这样展示你对贪心策略的理解：先说明你的贪心策略，用一两句话解释为什么局部最优能推出全局最优，紧接着构造一个反例，说明如果不这样做会失效。即使反例构造得不完美，这种思考方式本身就比“我猜应该这样”有说服力得多。
我常用的检验方法是一个三步流程：写出贪心选择规则；构造反例；如果找不到反例，就用数学归纳法的思路在脑海里过一遍证明。这套方法虽然不如完整证明严谨，但在实际解题和面试中非常高效。
6.4 贪心与二分、排序、双指针的组合
贪心算法很少独立出现，更多时候是和其它基础技巧配合。比如：
- 贪心 + 排序：区间调度类题目的标配。
- 贪心 + 双指针：分发饼干、四数相加等匹配问题。
- 贪心 + 二分查找：一些“最大化最小值”类问题，比如分配蛋糕、放置球等。
掌握这种组合思路，会大幅提高解题速度。看到题目之后，先判断“这是不是贪心能解决的问题”，再判断“我需要用什么辅助手段配合”。很多中等难度的贪心题，拆解开来就是“排序 + 一次遍历”，之所以被归类到中等，只是因为识别出贪心策略本身需要经验。
6.5 常见典型问题速查与避坑要点
我用一个表格整理了刷题过程中最常见的坑和对应建议，方便你快速查阅：
| 场景 | 常见误区 | 正确做法 |
|---|---|---|
| 区间重叠 | 按左端点排序 | 按右端点排序，贪心选择给未来留最大空间 |
| 天平称重 | 直接比较大小 | 优先比较剩余空间而非原始大小 |
| 跳跃游戏 | 只看当前步能跳多远 | 维护全局最远可达范围，局部更新 |
| 加油站 | 枚举所有起点 | 用总油量和当前油量双变量游标扫描 |
| 找零问题 | 优先用面额大钞票 | 考虑找零场景中面额不同灵活度 |
| 树形覆盖 | 从上到下安装 | 从叶子节点父节点自底向上覆盖 |
| 数字递增 | 直接替换数字为9 | 从右往左修正，避免连锁破坏 |
| 溢出处理 | 忽略int范围 | 用double或更大类型，提前评估数据范围 |
这个表格是我刷完这些题目之后自己总结的，几乎每一条背后都有一次Accepted到Wrong Answer的流泪经历。提前避开，你的刷题效率会提升很多。
7. 在LeetCode之外的贪心练习建议
7.1 如何判断一道题能不能用贪心
这是最常被问到的问题，我的经验是三个层面判断：
- 能不能构造反例？如果短时间内构造不出来，倾向于可以先试试贪心。
- 问题是否要求“最值”？不是所有最值问题都能贪心，但如果每一步的选择是独立的，不限制未来的选择空间，贪心大概率可行。
- 题目是否具有“不可逆”的特性？贪心要求选择一旦做出就不能回退。如果问题的解要求全局统筹，比如0-1背包，贪心往往失效。
实际刷题久了，你会形成一种题感：看到“最多”“最少”“最大”“最小”这样的词，先考虑排序，再考虑能不能维护一个游标或边界变量，如果能，大概率就是贪心思路。
7.2 推荐练习顺序和自查路径
如果是从零开始系统练习贪心，我建议按照下面的顺序：
- 分发饼干，理解排序加双指针的基础模型。
- 摆动序列，理解状态转换与计数。
- 跳跃游戏，理解可达性的区间扩张。
- 柠檬水找零，理解优先级的合理设计。
- 加油站，理解全局约束下的起点选择。
- 无重叠区间，理解区间调度的排序规则。
- 划分字母区间，理解贪心与哈希表的结合。
- 合并区间，理解覆盖合并的边界处理。
- 单调递增的数字，理解数字位上的贪心修正。
- 监控二叉树，理解树形结构上的贪心与状态设计。
每道题至少做三遍：第一遍独立想，想不出来直接看题解，但必须看懂思路而不是背代码；第二遍自己写代码，提交通过；第三遍隔几天重做，检验自己是否真的理解了贪心策略的推导过程。
7.3 我在实际练习中的几个体会
刷贪心算法这一个月，我的一个最大感受是：贪心算法的代码往往很短，但每一行都是思考铸成的。不要因为代码短就轻视它，也不要因为一次Wrong Answer就怀疑自己的智商。很多正确思路都是调试出来的，重要的是调试过程中你理解了为什么这个策略成立、那个策略不成立。
另一个体会是：贪心与其它算法结合的能力非常值钱。现在很多公司的面试题，表面上是贪心，实际上是“排序 + 双指针 + 贪心判断”的组合题。只背模板是绝对不够的，要在练习中主动去识别每一种组合模式。
如果你已经能独立推导上面表格中那些经典题目的贪心策略，可以将目光投向更多实战应用：比如Kruskal最小生成树、霍夫曼树的构造、分数背包问题。这些都是贪心思想的最佳实践场，把这些搞透，你对“局部最优到全局最优”的理解会上一个新台阶。
算法学习是一场长跑，day28只是过程中很普通的一天。但贪心算法这个主题，涵盖了从入门到进阶的非常多思维训练点，值得你认认真真花几天去消化。我写这篇文章时尽量把那些“老师没空讲、书上不写清、自己踩了才知道”的细节都摊开来了，希望对你有所帮助。
