算法精讲--贪心算法（一）：小白也能看懂的解题秘籍
·
算法精讲–贪心算法（一）：小白也能看懂的解题秘籍 🧩
🚀 创作不易，点赞关注是对作者最好的鼓励！
📝 欢迎大家与我交流学习，共同进步！
前言：开启算法修仙之路 🌟
🧠 为什么选择贪心算法？
▎算法江湖生存法则
在算法世界中，贪心算法犹如一把锋利的手术刀：
- ✨ 四两拨千斤：用简单策略解决复杂问题
- ⚡ 效率之王：时间复杂度往往最优
- 🧩 思维体操：培养最优决策直觉
一、走进贪心世界：从生活到算法 🌍
1.1 日常中的贪心智慧
还有更多场景如下：
- 🍔 自助餐策略：先拿最贵的海鲜
- 🚕 打车选择：接单最快的司机
- 📦 快递打包：优先装体积最大的物品
- 🚦 交通信号灯控制 ：动态调整绿灯时长缓解拥堵
- 🏥 急诊分诊系统 ：优先处理危重病人
- 📶 WiFi信道选择 ：自动切换干扰最小的频段
1.2 算法定义
决策流程图
1.3 对比其他算法
| 特征 | 贪心算法 | 暴力枚举 | 动态规划 |
|---|---|---|---|
| 时间复杂度 | O(n log n) | O(2^n) | O(n²) |
| 空间复杂度 | O(1) | O(n) | O(n) |
| 是否需要历史信息 | 不需要 | 需要 | 需要 |
| 典型应用 | 最小生成树 | 密码破解 | 背包问题 |
二、贪心算法深度解构 🔍
2.1 核心特征三重奏
-
局部最优性 🎯：每个决策都是当前最佳选择
// 伪代码示例 while(未解决问题){ 选择当前最优解; 更新问题状态; } -
无后效性 ⚡：决策不影响后续状态
- 高效性 🚀：通常时间复杂度为 O(n log n)
2.2 适用场景雷达图
2.3 与动态规划的"爱恨情仇"
| 对比维度 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策影响 | 无后效性 | 有状态转移 |
| 时间复杂度 | O(n log n) | O(n^2) |
| 空间复杂度 | O(1) | O(n) |
| 典型问题 | 霍夫曼编码 | 0-1背包问题 |
| 验证方式 | 数学归纳法 | 状态转移方程 |
- 贪心算法是在每一步选择中都采取当前状态下最优决策的算法范式。它与动态规划的区别就像：
三、五大经典问题详解 🏆
通用贪心模板
public class GreedyTemplate {
// 🎯 解题四步法
public void solveProblem(int[] input) {
// Step 1: 预处理排序 🌈
Arrays.sort(input);
// Step 2: 初始化关键变量 🔑
int result = 0;
int currentState = 0;
// Step 3: 贪心遍历决策 🌟
for (int i = 0; i < input.length; i++) {
currentState = updateState(input[i], currentState);
if (needTakeAction(currentState)) {
result++;
currentState = resetState();
}
}
// Step 4: 返回最终结果 🏆
System.out.println("最优解: " + result);
}
// 辅助方法示例
private int updateState(int value, int current) {
return Math.max(current, value);
}
private boolean needTakeAction(int state) {
return state >= 5; // 自定义触发条件
}
}
3.1 简单级：分糖果问题 🍬
LeetCode 455：分发饼干
解题四部曲：
- 排序处理：将孩子和饼干数组排序
- 双指针扫描：类似合并有序数组
- 贪心匹配：用最小饼干满足最小需求
- 统计结果：计算满足的孩子数
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g); // O(n log n)
Arrays.sort(s); // O(m log m)
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) i++; // 满足当前孩子
j++; // 无论是否满足都移动饼干指针
}
return i;
}
复杂度分析：
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 数组排序 | O(n log n) | O(log n) |
| 双指针遍历 | O(n) | O(1) |
3.2 进阶级：跳跃游戏 🦘
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]);
if (maxReach >= nums.length - 1) return true; // 提前终止
}
return true;
}
算法流程图：
3.3 变形题：加油站之谜 ⛽
LeetCode 134：加油站
贪心策略：
- 总油量检查：如果总油量 < 总消耗，直接返回-1
- 局部油量监控：当当前油量<0时重置起点
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, curr = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
total += gas[i] - cost[i];
curr += gas[i] - cost[i];
if (curr < 0) { // 当前油量不足
start = i + 1; // 重置起点
curr = 0; // 清空油量
}
}
return total >= 0 ? start : -1;
}
变量追踪表：
| 变量 | 作用 | 更新条件 |
|---|---|---|
| total | 总油量差值 | 每次循环累加 |
| curr | 当前油箱剩余量 | 每次循环累加 |
| start | 可能的起点位置 | curr<0时更新 |
3.4 中等级：时间管理大师 ⏰
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;
}
复杂度对比：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 贪心算法 | O(n log n) | O(1) | 区间调度 |
| 动态规划 | O(n²) | O(n) | 带权区间选择 |
3.5 困难级：任务调度器 📅
LeetCode 621：任务调度器
贪心策略图解：
分步实现：
- 频率统计：记录每种任务出现次数
- 排序处理：按频率降序排序
- 框架构建：计算最小时间框架
- 特殊处理：处理多个最高频任务的情况
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;
Arrays.sort(freq); // O(1)时间排序（固定26长度）
int maxFreq = freq[25];
int idleSlots = (maxFreq - 1) * n;
for (int i = 24; i >= 0 && freq[i] > 0; i--) {
idleSlots -= Math.min(freq[i], maxFreq - 1);
}
return tasks.length + Math.max(0, idleSlots);
}
变量追踪表：
| 变量 | 作用 | 更新规则 |
|---|---|---|
freq | 存储任务频率 | 遍历任务数组统计 |
maxFreq | 记录最高任务频率 | 取排序后最后一个元素 |
idleSlots | 计算理论待命时间 | (maxFreq-1)*n - 填充其他任务 |
Math.max() | 处理负值的待命时间 | 确保不出现负数 |
四、贪心算法全维度剖析 🔬
4.1 正确性证明三大法（深度扩展）
1. 数学归纳法实战演示
以跳跃游戏为例证明贪心策略的正确性：
命题：若存在可达路径，贪心算法必能找到
基例：n=1时显然成立
假设：对于长度为k的数组成立
递推：当数组长度为k+1时
1. 根据贪心策略，max_reach ≥ k
2. 由假设可知前k步可达
3. 因此第k+1步必然可达
2. 交换论证法图解
假设存在更优解，通过元素交换推导矛盾：
3. 拟阵理论应用场景
4.2 效率优化秘籍
| 优化技巧 | 代码示例 | 适用场景 | 性能提升 |
|---|---|---|---|
| 预处理排序 | Arrays.sort(intervals) | 区间类问题 | O(n²)→O(n log n) |
| 剪枝策略 | if(max_reach >= end) break | 跳跃游戏类 | 减少50%遍历次数 |
| 空间压缩 | 使用 while替代递归 | 所有贪心问题 | 避免栈溢出 |
内存优化实例：
// 优化前（使用额外空间）
List<Integer> list = new ArrayList<>();
// 优化后（原地操作）
int index = 0;
for(int num : nums){
if(condition) nums[index++] = num;
}
4.3 错误类型全解析
1. 经典错误代码示例
// 错误的硬币问题解法（未排序处理）
public int coinChange(int[] coins, int amount) {
int count = 0; // 🚫 错误！未排序导致局部最优≠全局最优
for(int coin : coins){
while(amount >= coin){
amount -= coin;
count++;
}
}
return amount == 0 ? count : -1;
}
2. 错误类型对照表
| 错误现象 | 典型案例 | 修正方法 |
|---|---|---|
| 排序策略错误 | 跳跃游戏II | 按起始位置排序 |
| 边界处理遗漏 | 分发饼干 | 增加 g.length==0判断 |
| 更新策略错误 | 加油站问题 | 重置curr时更新start |
五、实战训练营 🏋️（全面升级）
5.1 新手村任务（扩展详解）
1. 柠檬水找零 🍋
核心技巧：优先使用大面额纸币
2. 摆动序列 📈
关键逻辑：
if 当前差值 > 0 ≠ 上次差值 > 0:
result += 1
更新上次差值
3. 最大子序和 💰
贪心策略：
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for(int num : nums){
currentSum = Math.max(num, currentSum + num); // ✨ 即时取舍
maxSum = Math.max(maxSum, currentSum);
}
5.2 高手挑战
典型题解：任务调度器
5.3 自测题库（新增分类训练）
| 题型分类 | 推荐题目 | 难度 | 核心考点 |
|---|---|---|---|
| 区间问题 | 用最少数箭引爆气球 | 🟠 | 端点排序 |
| 字符串操作 | 分割平衡字符串 | 🟢 | 状态计数 |
| 游戏策略 | 移掉K位数字 | 🟠 | 单调栈 |
| 高级调度 | 课程表III | 🟠 | 优先队列 |
六、灵魂拷问区 ❓
Q1：如何识别贪心算法适用场景？
三维判断法：
- 最优子结构：问题的最优解包含子问题的最优解
- 贪心选择性质：局部最优能导致全局最优
- 无后效性：决策不影响后续状态
Q2：为什么硬币问题有时贪心失效？
当硬币面额不满足贪心友好条件时（如美国硬币体系1,5,10,25是友好的，但若存在面额4，则凑6元时会失效）：
- 贪心解：4+1+1（3枚）
- 最优解：3+3（2枚）
🌟 下期预告：《贪心算法（二）：区间问题的艺术》 我们将深入探讨时间管理大师的算法奥秘，揭开区间调度、合并、交集的终极解法！
更多推荐
33
0- 0
已为社区贡献6条内容
所有评论(0)