第24篇-贪心算法入门-为什么局部最优有时能得到全局最优

概述为什么贪心题看起来简单却总有人做错上一篇我们学习了堆与优先队列重点是如何高效维护 TopK、动态最值和多路合并。这一篇我们进入另一个核心专题贪心算法。很多人第一次接触贪心时会觉得它很直观先选当前最优的能早结束就早结束能少占资源就少占资源但真正做题时最容易出问题的地方恰恰是你怎么证明“当前最优”真的不会把后面搞坏贪心不是“凭感觉选最优”而是要满足某种结构条件。当题目具备这些条件时局部最优才可能推出全局最优。本篇文章会围绕下面几类典型问题展开贪心到底是什么什么时候能用贪心区间类贪心跳跃类贪心分配与优化类贪心常见坑点和判断方法学完这篇你应该能识别常见贪心题型并能写出区间调度、跳跃游戏和局部最优选择类问题的基本模板。核心概念贪心到底是什么贪心算法的核心思想是每一步都做当前看起来最优的选择这个“当前最优”通常指尽量早结束尽量少占用资源尽量留下更多空间尽量让后续选择更自由贪心和动态规划的区别这两个概念很容易混淆。对比项贪心动态规划选择方式每一步选当前最优枚举状态并保存历史最优是否回退通常不回退明确记录子问题答案适用场景局部最优能推出全局最优子问题重叠且需要全局比较实现特点简洁更系统通常更复杂可以简单记成贪心是“走一步看一步”DP 是“把所有可能算清楚”但贪心并不比 DP 简单。难点就在于你必须确认局部最优不会影响全局最优。贪心每一步只做当前最优选择关键在于这种选择是否能长期成立。什么时候可以考虑贪心看到题目时如果有下面这些特征可以优先想贪心让你求最大数量、最少次数、最少资源每一步只会影响后续可选空间题目和区间、排序、选择、覆盖有关需要按某种规则依次做决定常见关键词包括最少最多覆盖选择排序后处理区间不重叠尽量早结束一个简单判断方法如果题目问在不破坏后续选择的前提下当前该怎么选最好那很可能可以考虑贪心。如果题目强调“当前选择会影响后续空间”通常就值得先想贪心。题型一区间调度问题区间类贪心是最经典的一类题。题目通常会写成给你一些区间最多能选多少个互不重叠的区间或者删除最少多少个区间使剩下的区间互不重叠核心思路区间类贪心最重要的策略是优先保留结束时间最早的区间为什么因为结束越早后面越容易接上更多区间。这样能给后续留出最大的选择空间。例子区间如下[1, 3], [2, 4], [3, 5], [6, 7]如果按结束时间排序[1, 3], [2, 4], [3, 5], [6, 7]先选[1, 3]然后能接上[6, 7]共选2个。如果先选[2, 4]后面能接的区间可能更少。为什么按结束时间排序按结束时间最早排序能让当前区间尽快结束从而最大化后续选择空间。这是区间贪心的经典证明思路。Java 代码实现importjava.util.Arrays;classSolution{publicinteraseOverlapIntervals(int[][]intervals){if(intervals.length0){return0;}Arrays.sort(intervals,(a,b)-a[1]-b[1]);intcount1;intendintervals[0][1];for(inti1;iintervals.length;i){if(intervals[i][0]end){count;endintervals[i][1];}}returnintervals.length-count;}}代码怎么理解end表示当前已经选中的最后一个区间的结束位置。如果下一个区间的起点大于等于end说明它和当前区间不重叠可以接上。如果重叠就跳过当前区间继续看后面的区间。区间类贪心常按结束时间排序因为结束越早后续空间越大。题型二最少箭射爆气球题目给定若干气球区间每支箭可以射穿一个点问最少需要几支箭才能射爆所有气球。这类题本质上也是区间覆盖。解题思路如果两个区间有交集那么一支箭可以同时射爆它们。所以我们按区间结束位置排序先选一个结束最早的区间尝试让后面的区间尽量和它重叠一旦不重叠就需要新箭Java 代码实现importjava.util.Arrays;classSolution{publicintfindMinArrowShots(int[][]points){if(points.length0){return0;}Arrays.sort(points,(a,b)-Integer.compare(a[1],b[1]));intarrows1;longendpoints[0][1];for(inti1;ipoints.length;i){if(points[i][0]end){arrows;endpoints[i][1];}}returnarrows;}}为什么这里是不是气球区间通常是闭区间。如果一个气球的起点等于箭的位置也算被射中。所以只有在当前气球起点 已有箭的位置时才需要新箭。闭区间覆盖题要特别注意边界是否重叠取决于题目对端点的定义。题型三跳跃游戏跳跃游戏也是很典型的贪心题。题目通常是给定数组nums每个位置表示从当前位置最多能跳多远判断是否能跳到最后一个位置。核心思路维护一个变量当前能到达的最远位置遍历数组时不断更新这个最远位置far max(far, i nums[i])如果遍历到某个位置i时发现i far说明这个位置根本到不了直接返回false。Java 代码实现classSolution{publicbooleancanJump(int[]nums){intfar0;for(inti0;inums.length;i){if(ifar){returnfalse;}farMath.max(far,inums[i]);}returntrue;}}为什么不用真的模拟跳很多人第一反应是从每个位置尝试跳很多步。但这样会引入大量重复判断。实际上我们只关心当前位置能把最远范围推进到哪里只要最远范围一直能覆盖到终点就说明能跳到最后。跳跃类贪心不需要真的每次跳关键是维护当前最远可达范围。题型四跳跃游戏 II题目给定数组nums每个位置表示最多能跳的步数求跳到最后一个位置的最少跳跃次数。这道题比上一题更进一步。上一题只问“能不能到”这一题问“最少几步到”。核心思路把问题看成一层一层推进当前跳数能覆盖一个范围在这个范围内继续找下一跳能到的最远位置当走到当前范围边界时跳数加一并更新新范围Java 代码实现classSolution{publicintjump(int[]nums){intsteps0;intcurrentEnd0;intfar0;for(inti0;inums.length-1;i){farMath.max(far,inums[i]);if(icurrentEnd){steps;currentEndfar;}}returnsteps;}}代码怎么理解currentEnd表示当前这一步跳跃所能覆盖的边界。在这段区间内我们不断更新下一步能到的最远位置far。一旦遍历到currentEnd说明这一跳的选择已经结束需要再跳一次并把边界更新成far。这和 BFS 按层扩展的思路非常像。最少跳跃次数可以看成按层推进每一层对应一次跳跃。题型五分发糖果题目每个孩子至少分到一颗糖果相邻孩子评分高的必须分得更多求最少糖果数量。这类题也很适合用贪心。核心思路通常需要两次遍历从左到右处理左边约束从右到左处理右边约束最后取两边约束的较大值。Java 代码实现classSolution{publicintcandy(int[]ratings){intnratings.length;int[]candiesnewint[n];for(inti0;in;i){candies[i]1;}for(inti1;in;i){if(ratings[i]ratings[i-1]){candies[i]candies[i-1]1;}}for(intin-2;i0;i--){if(ratings[i]ratings[i1]){candies[i]Math.max(candies[i],candies[i1]1);}}intsum0;for(intcandy:candies){sumcandy;}returnsum;}}为什么要两次遍历左到右只能保证当前孩子比左边高时糖果更多右到左只能保证当前孩子比右边高时糖果更多两个方向的约束都要满足所以最后取最大值。有左右双向约束时常用两次贪心扫描分别处理再取较大值。题型六按照规则选择最优序列有些贪心题不一定是区间或跳跃但也会有一个核心先排序再按某个局部规则选择。比如按截止时间安排任务按价值密度选物品按字符串规则拼接这类题的共同点是排序负责建立选择顺序贪心负责在这个顺序上做局部决策一个简单模板Arrays.sort(items,comparator);for(Itemitem:items){if(满足选择条件){选择当前项;}}但这类题最重要的不是代码模板而是你要证明为什么这个排序顺序不会错当题目允许先排序时贪心往往是在排序后的顺序上做局部最优选择。为什么贪心有时正确这是贪心题最核心的问题。并不是所有“看起来最优”的选择都成立。贪心正确通常依赖下面几种结构1. 局部选择不会破坏未来最优比如区间调度里选结束最早的区间能给后面留下最多空间。2. 选择具有交换性如果把某个非最优选择换成更优选择不会让答案变差那么贪心就可能成立。3. 问题具备单调性比如跳跃游戏中“能到达的最远位置”只会越来越远不会倒退。4. 题目本身是在做约束下的最优选择例如最少箭、最少糖果、最多不重叠区间本质都在找一种全局资源最省的方案。贪心之所以能成立通常是因为局部更优不会破坏后续结构甚至会给后续留下更多空间。贪心题最容易错在哪里1. 排序依据写错区间问题里很多人会误按起点排序。但经典区间调度通常应该按结束时间排序。2. 边界条件没看清比如区间是开区间还是闭区间会影响这种判断的写法。3. 把贪心题写成暴力能用一个变量维护最优边界时不要把每个选择分支都展开。4. 题目实际上不满足贪心条件有些题看起来像选择问题实际上需要动态规划。如果局部最优和全局最优之间没有明确关系别强行贪心。5. 忽略“选择后状态变化”贪心每一步选完后状态可能变化很大。你要确认这种状态变化是否可控、是否单调。复杂度分析贪心通常为什么快很多贪心题之所以快是因为它们只需要排序一次再线性扫描一次因此常见复杂度是O(n log n)如果不需要排序可能就是O(n)典型复杂度对比问题类型常见做法复杂度区间调度排序 一次扫描O(n log n)跳跃游戏单次扫描O(n)糖果分配两次扫描O(n)贪心题的重点不在复杂度多花哨而在于用最少的状态做最少的判断模板总结贪心题怎么想遇到贪心题时可以按下面顺序思考题目要最大、最小、最少还是最多当前选择会不会影响后续空间能不能排序排序后该按什么规则选选完后状态如何更新是否需要证明局部最优成立贪心常用模板Arrays.sort(items,comparator);intans0;intstateinitialState;for(Itemitem:items){if(canChoose(item,state)){ans;updateState(item,state);}}returnans;判断题目能否贪心的简化句如果我现在选得更好会不会让后面更差如果答案是“不会”那就值得继续往贪心方向想。总结贪心算法不是“随便选一个看起来不错的”而是依赖题目结构的选择策略。你可以重点记住下面几句话贪心是每一步做当前最优选择真正难点是证明这个选择不会破坏全局最优区间题常按结束时间排序跳跃题常维护当前最远可达位置双向约束题常用两次扫描排序后再做局部决策是贪心的常见套路如果不能说明局部最优为何成立就不要强行用贪心贪心题通常代码不长但思路证明很重要下一篇我们会进入动态规划入门从爬楼梯和状态转移开始把“如何定义状态”这件事讲清楚。