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

概述：为什么贪心题看起来简单，却总有人做错

上一篇我们学习了堆与优先队列，重点是如何高效维护 TopK、动态最值和多路合并。

这一篇我们进入另一个核心专题：贪心算法。

很多人第一次接触贪心时，会觉得它很直观：

• 先选当前最优的
• 能早结束就早结束
• 能少占资源就少占资源

但真正做题时，最容易出问题的地方恰恰是：

你怎么证明“当前最优”真的不会把后面搞坏

贪心不是“凭感觉选最优”，而是要满足某种结构条件。
当题目具备这些条件时，局部最优才可能推出全局最优。

本篇文章会围绕下面几类典型问题展开：

1. 贪心到底是什么
2. 什么时候能用贪心
3. 区间类贪心
4. 跳跃类贪心
5. 分配与优化类贪心
6. 常见坑点和判断方法

学完这篇，你应该能识别常见贪心题型，并能写出区间调度、跳跃游戏和局部最优选择类问题的基本模板。

核心概念：贪心到底是什么

贪心算法的核心思想是：

每一步都做当前看起来最优的选择

这个“当前最优”通常指：

• 尽量早结束
• 尽量少占用资源
• 尽量留下更多空间
• 尽量让后续选择更自由

贪心和动态规划的区别

这两个概念很容易混淆。

可以简单记成：

贪心是“走一步看一步”，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.length==0){return0;}Arrays.sort(intervals,(a,b)->a[1]-b[1]);intcount=1;intend=intervals[0][1];for(inti=1;i<intervals.length;i++){if(intervals[i][0]>=end){count++;end=intervals[i][1];}}returnintervals.length-count;}}

代码怎么理解

end表示当前已经选中的最后一个区间的结束位置。

如果下一个区间的起点大于等于end，说明它和当前区间不重叠，可以接上。

如果重叠，就跳过当前区间，继续看后面的区间。

区间类贪心常按结束时间排序，因为结束越早，后续空间越大。

题型二：最少箭射爆气球

题目：

给定若干气球区间，每支箭可以射穿一个点，问最少需要几支箭才能射爆所有气球。

这类题本质上也是区间覆盖。

解题思路

如果两个区间有交集，那么一支箭可以同时射爆它们。

所以我们按区间结束位置排序：

1. 先选一个结束最早的区间
2. 尝试让后面的区间尽量和它重叠
3. 一旦不重叠，就需要新箭

Java 代码实现

importjava.util.Arrays;classSolution{publicintfindMinArrowShots(int[][]points){if(points.length==0){return0;}Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));intarrows=1;longend=points[0][1];for(inti=1;i<points.length;i++){if(points[i][0]>end){arrows++;end=points[i][1];}}returnarrows;}}

为什么这里是>不是>=

气球区间通常是闭区间。
如果一个气球的起点等于箭的位置，也算被射中。

所以只有在：

当前气球起点 > 已有箭的位置

时，才需要新箭。

闭区间覆盖题要特别注意边界，是否重叠取决于题目对端点的定义。

题型三：跳跃游戏

跳跃游戏也是很典型的贪心题。

题目通常是：

给定数组nums，每个位置表示从当前位置最多能跳多远，判断是否能跳到最后一个位置。

核心思路

维护一个变量：

当前能到达的最远位置

遍历数组时，不断更新这个最远位置：

far = max(far, i + nums[i])

如果遍历到某个位置i时，发现i > far，说明这个位置根本到不了，直接返回false。

Java 代码实现

classSolution{publicbooleancanJump(int[]nums){intfar=0;for(inti=0;i<nums.length;i++){if(i>far){returnfalse;}far=Math.max(far,i+nums[i]);}returntrue;}}

为什么不用真的模拟跳

很多人第一反应是从每个位置尝试跳很多步。
但这样会引入大量重复判断。

实际上我们只关心：

当前位置能把最远范围推进到哪里

只要最远范围一直能覆盖到终点，就说明能跳到最后。

跳跃类贪心不需要真的每次跳，关键是维护当前最远可达范围。

题型四：跳跃游戏 II

题目：

给定数组nums，每个位置表示最多能跳的步数，求跳到最后一个位置的最少跳跃次数。

这道题比上一题更进一步。
上一题只问“能不能到”，这一题问“最少几步到”。

核心思路

把问题看成一层一层推进：

• 当前跳数能覆盖一个范围
• 在这个范围内，继续找下一跳能到的最远位置
• 当走到当前范围边界时，跳数加一，并更新新范围

Java 代码实现

classSolution{publicintjump(int[]nums){intsteps=0;intcurrentEnd=0;intfar=0;for(inti=0;i<nums.length-1;i++){far=Math.max(far,i+nums[i]);if(i==currentEnd){steps++;currentEnd=far;}}returnsteps;}}

代码怎么理解

currentEnd表示当前这一步跳跃所能覆盖的边界。
在这段区间内，我们不断更新下一步能到的最远位置far。

一旦遍历到currentEnd，说明这一跳的选择已经结束，需要再跳一次，并把边界更新成far。

这和 BFS 按层扩展的思路非常像。

最少跳跃次数可以看成按层推进，每一层对应一次跳跃。

题型五：分发糖果

题目：

每个孩子至少分到一颗糖果，相邻孩子评分高的必须分得更多，求最少糖果数量。

这类题也很适合用贪心。

核心思路

通常需要两次遍历：

1. 从左到右，处理左边约束
2. 从右到左，处理右边约束

最后取两边约束的较大值。

Java 代码实现

classSolution{publicintcandy(int[]ratings){intn=ratings.length;int[]candies=newint[n];for(inti=0;i<n;i++){candies[i]=1;}for(inti=1;i<n;i++){if(ratings[i]>ratings[i-1]){candies[i]=candies[i-1]+1;}}for(inti=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candies[i]=Math.max(candies[i],candies[i+1]+1);}}intsum=0;for(intcandy:candies){sum+=candy;}returnsum;}}

为什么要两次遍历

左到右只能保证：

当前孩子比左边高时，糖果更多

右到左只能保证：

当前孩子比右边高时，糖果更多

两个方向的约束都要满足，所以最后取最大值。

有左右双向约束时，常用两次贪心扫描分别处理，再取较大值。

题型六：按照规则选择最优序列

有些贪心题不一定是区间或跳跃，但也会有一个核心：
先排序，再按某个局部规则选择。

比如：

• 按截止时间安排任务
• 按价值密度选物品
• 按字符串规则拼接

这类题的共同点是：

排序负责建立选择顺序，贪心负责在这个顺序上做局部决策

一个简单模板

Arrays.sort(items,comparator);for(Itemitem:items){if(满足选择条件){选择当前项;}}

但这类题最重要的不是代码模板，而是你要证明：

为什么这个排序顺序不会错

当题目允许先排序时，贪心往往是在排序后的顺序上做局部最优选择。

为什么贪心有时正确

这是贪心题最核心的问题。

并不是所有“看起来最优”的选择都成立。
贪心正确通常依赖下面几种结构：

1. 局部选择不会破坏未来最优

比如区间调度里，选结束最早的区间，能给后面留下最多空间。

2. 选择具有交换性

如果把某个非最优选择换成更优选择，不会让答案变差，那么贪心就可能成立。

3. 问题具备单调性

比如跳跃游戏中，“能到达的最远位置”只会越来越远，不会倒退。

4. 题目本身是在做约束下的最优选择

例如最少箭、最少糖果、最多不重叠区间，本质都在找一种全局资源最省的方案。

贪心之所以能成立，通常是因为局部更优不会破坏后续结构，甚至会给后续留下更多空间。

贪心题最容易错在哪里

1. 排序依据写错

区间问题里，很多人会误按起点排序。
但经典区间调度通常应该按结束时间排序。

2. 边界条件没看清

比如区间是开区间还是闭区间，会影响：

• >=
• >

这种判断的写法。

3. 把贪心题写成暴力

能用一个变量维护最优边界时，不要把每个选择分支都展开。

4. 题目实际上不满足贪心条件

有些题看起来像选择问题，实际上需要动态规划。
如果局部最优和全局最优之间没有明确关系，别强行贪心。

5. 忽略“选择后状态变化”

贪心每一步选完后，状态可能变化很大。
你要确认这种状态变化是否可控、是否单调。

复杂度分析：贪心通常为什么快

很多贪心题之所以快，是因为它们只需要：

• 排序一次
• 再线性扫描一次

因此常见复杂度是：

O(n log n)

如果不需要排序，可能就是：

O(n)

典型复杂度对比

贪心题的重点不在复杂度多花哨，而在于：

用最少的状态，做最少的判断

模板总结：贪心题怎么想

遇到贪心题时，可以按下面顺序思考：

1. 题目要最大、最小、最少还是最多
2. 当前选择会不会影响后续空间
3. 能不能排序
4. 排序后该按什么规则选
5. 选完后状态如何更新
6. 是否需要证明局部最优成立

贪心常用模板

Arrays.sort(items,comparator);intans=0;intstate=initialState;for(Itemitem:items){if(canChoose(item,state)){ans++;updateState(item,state);}}returnans;

判断题目能否贪心的简化句

如果我现在选得更好，会不会让后面更差？

如果答案是“不会”，那就值得继续往贪心方向想。

总结

贪心算法不是“随便选一个看起来不错的”，而是依赖题目结构的选择策略。

你可以重点记住下面几句话：

• 贪心是每一步做当前最优选择
• 真正难点是证明这个选择不会破坏全局最优
• 区间题常按结束时间排序
• 跳跃题常维护当前最远可达位置
• 双向约束题常用两次扫描
• 排序后再做局部决策是贪心的常见套路
• 如果不能说明局部最优为何成立，就不要强行用贪心
• 贪心题通常代码不长，但思路证明很重要

下一篇我们会进入动态规划入门，从爬楼梯和状态转移开始，把“如何定义状态”这件事讲清楚。