好问题 👍，我给你系统讲一下 Greedy（贪心）算法。
🔑 什么是 Greedy 算法？
Greedy（贪心）算法是一种 逐步构建答案的算法思想：
- 在每一步，都选择当前看起来 最优的局部选择（局部最优解）
- 希望通过一系列局部最优选择，最终得到 全局最优解
它 不回溯、不穷举，而是依赖“局部最优能推出整体最优”的前提。
📘 经典例子
- 找零钱问题
- 面额：1, 5, 10, 20, 50, 100
- 找 187 元 → 每次尽量用最大面额：100 → 50 → 20 → 10 → 5 → 1 → 1
- 总共 7 张。 👉 因为这种货币体系是“规范化的”，贪心一定能得到最优解。
- 活动选择（区间调度）
- 给一堆活动，每个活动有开始时间和结束时间。
- 想选最多的活动且不能重叠。
- 策略：按结束时间最早排序，每次选能参加的活动。 👉 这是贪心算法的经典应用。
- LeetCode 861. Score After Flipping Matrix
- 思路：第一列必须全 1（局部最优保证整体更大），再逐列保证 1 比 0 多。 👉 就是贪心。
⚡ Greedy 适合解决的问题
Greedy 并不是万能的，适用场景一般有两个条件：
- 贪心选择性质 (Greedy Choice Property)
- 全局最优解可以通过一系列局部最优选择得到。
- 例子：区间调度、找零钱（规范货币体系）。
- 最优子结构 (Optimal Substructure)
- 问题的最优解包含其子问题的最优解。
- 例子：活动选择问题。
🚫 贪心不适合的情况
- 如果全局最优解 ≠ 局部最优解累积。
-
比如：0/1 背包问题。
- 物品价值和重量不同，不能拆分。
- 如果总重量 10，选物品时不能简单贪心选“单位价值最大”的 → 可能错。
- 这种问题要用 动态规划（DP）。
✅ 总结
- Greedy = 每一步都做当前最优的选择。
- 适合 局部最优 = 全局最优 的问题。
- 常见应用：找零钱、区间调度、哈夫曼编码、最小生成树（Prim/Kruskal）、Dijkstra 最短路。
好 👍，我给你整理一份 经典贪心算法题目清单，涵盖 LeetCode 和常见面试题，分门别类带上思路，方便你系统刷题。
🔥 经典贪心算法题目清单
1. 区间类（调度/覆盖/合并）
这类题目是贪心的“标配”，核心思想是：按某个顺序排序，再逐步选择。
435. Non-overlapping Intervals
删除最少的区间，使剩下的区间互不重叠。
👉 思路：按结束时间排序，每次尽量选结束早的。452. Minimum Number of Arrows to Burst Balloons
区间射气球，最少需要几支箭。
👉 思路：按区间右端点排序，一支箭能覆盖尽量多的气球。56. Merge Intervals
合并重叠区间。
👉 思路：按左端点排序，逐个合并。活动选择问题 (经典面试题)
选最多不重叠活动，按结束时间排序贪心。
2. 数组/序列操作
55. Jump Game
判断能否跳到终点。
👉 思路：维护最远能到达的位置，每一步尽量走最远。45. Jump Game II
最少跳几次到终点。
👉 思路：在当前覆盖范围内尽量扩展下一步最远。134. Gas Station
找出能否绕一圈加油站。
👉 思路：贪心地统计油量差，若能走一圈，从累积最低点后出发。376. Wiggle Subsequence
最长摆动子序列。
👉 思路：只要趋势发生变化（正负号变化），计数 +1。
3. 数字 / 二进制类
860. Lemonade Change
收钱找零，判断是否能顺利完成。
👉 思路：优先使用大额纸币（保留小额给后面）。861. Score After Flipping Matrix
翻转矩阵使得二进制数和最大。
👉 思路：保证第一列全 1，然后逐列保证 1 尽量多。1005. Maximize Sum Of Array After K Negations
取反 K 次使数组和最大。
👉 思路：每次翻转最小的数。
4. 字符串/调度类
621. Task Scheduler
CPU 调度任务，最小执行时间。
👉 思路：优先执行频率最高的任务，空闲时插入其他。402. Remove K Digits
删除 K 个数字得到最小数。
👉 思路：用栈，每次保证栈单调递增，不行就弹出前面的。763. Partition Labels
分割字符串，每段尽量大，使不同段的字符不重复。
👉 思路：贪心地按字符最后出现位置来切割。
5. 图/树中的贪心
- Prim / Kruskal 算法 → 最小生成树（MST）。
- Dijkstra 算法 → 单源最短路。 👉 它们本质上就是贪心，每次选择当前最短的边/路径。
✅ 总结
贪心题常见套路：
- 排序（按结束时间 / 开始时间 / 右端点）
- 局部最优选择（选最大 / 最小 / 最多 / 最少）
- 可行性验证（能走通 / 能覆盖 / 能找零）
Top comments (0)