一、上期回顾学完二维动态规划吃透网格路径问题与01 背包核心写法掌握二维状态转移与空间优化技巧。今天学习贪心算法思路最简单、代码最短、考场性价比极高。二、贪心算法核心定义贪心 每一步只做当前最优选择期望最终得到全局最优解只看眼前利益不考虑未来整体规划无需回溯、无需枚举、无需 DP 推导解题速度快、逻辑简单、代码量极少适用三大前提局部最优当前最优选择可行全局最优所有局部最优能拼成全局最优无后效性当前选择不会影响后续所有决策不适用场景局部最优无法推出全局最优 → 必须改用动态规划三、贪心通用解题四步确定贪心策略选最大 / 选最小 / 选最早 / 选最晚排序预处理绝大多数贪心题必须先排序依次遍历执行局部最优决策统计答案输出结果四、经典例题 1分发饼干入门必做题意孩子有胃口大小饼干有尺寸一块饼干满足一个孩子求最多满足几个孩子。贪心策略小饼干优先喂胃口小的孩子#include iostream #include vector #include algorithm using namespace std; int findContentChildren(vectorint g, vectorint s) { sort(g.begin(),g.end()); sort(s.begin(),s.end()); int i 0, j 0, cnt 0; while(i g.size() j s.size()) { if(s[j] g[i]) { cnt; i; j; } else j; } return cnt; }五、经典例题 2区间调度最多不重叠区间题意给出多个起止时间区间选出最多互不重叠区间贪心最优策略按结束时间从小到大排序优先选结束最早的int eraseOverlapIntervals(vectorvectorint intervals) { if(intervals.empty()) return 0; // 按结束时间排序 sort(intervals.begin(),intervals.end(),[](vectorinta,vectorintb){ return a[1] b[1]; }); int res 1; int lastEnd intervals[0][1]; for(int i 1; i intervals.size(); i) { if(intervals[i][0] lastEnd) { res; lastEnd intervals[i][1]; } } return intervals.size() - res; }六、经典例题 3跳跃游戏题意数组代表最远跳跃长度判断能否跳到最后贪心策略实时维护当前能跳到的最远距离bool canJump(vectorint nums) { int far 0; for(int i 0; i nums.size(); i) { if(i far) return false; far max(far, i nums[i]); } return true; }七、经典例题 4最大三角形周长贪心思路数组排序从大到小枚举三边满足abc即为最大周长int largestPerimeter(vectorint nums) { sort(nums.begin(),nums.end()); for(int i nums.size()-1; i 2; i--) { if(nums[i-2]nums[i-1] nums[i]) return nums[i]nums[i-1]nums[i-2]; } return 0; }八、高频贪心策略汇总背诵分配问题从小到大匹配小配小、大配大区间问题优先选结束早跳跃覆盖维护最远可达距离数值最值优先取最大 / 优先取最小费用最优优先选代价最低方案九、贪心 vs 动态规划 核心区别贪心直接局部最优无回溯无状态记录速度最快DP枚举所有状态记录最优结果可处理无法贪心的场景能贪心尽量贪心不能贪心再用 DP十、今日核心总结贪心核心局部最优 → 全局最优绝大多数题目第一步都是排序逻辑简单、代码简短、遍历一次即可完成确定正确贪心策略是做题唯一难点无法确定策略时立刻切换动态规划思路十一、课后练习独立默写分发饼干完整贪心代码手写跳跃游戏贪心解法尝试用贪心解决区间选点问题