Lazy loaded image
😋最易懂的贪心算法
Words 3018Read Time 8 min
2025-10-4
2025-10-4
type
status
date
slug
summary
tags
category
icon
password
网址
 

算法解释

顾名思义,贪心算法或贪心思想 (greedy algorithm) 采用贪心的策略,保证每次操作都是局部最优的,从而使最后得到的结果是全局最优的
举一个最简单的例子:小明和小王喜欢吃苹果,小明可以吃五个,小王可以吃三个。已知苹果园里有吃不完的苹果,求小明和小王一共最多吃多少个苹果。在这个例子中,我们可以选用的贪心策略为,每个人吃自己能吃的最多数量的苹果,这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和,且局部结果互不相干,因此局部最优的策略同样是全局最优的。证明一道题能用贪心算法解决,有时远比用贪心算法解决该题更复杂。一般情况下,在简单操作后,具有明显的从局部到整体的递推关系,或者可以通过数学归纳法推测结果时,我们才会使用贪心算法。

分配问题

题目描述

有一群孩子和一堆饼干,每个孩子有一个饥饿度,每个饼干都有一个饱腹度。每个孩子只能吃一个饼干,且只有饼干的饱腹度不小于孩子的饥饿度时,这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例

输入两个数组,分别代表孩子的饥饿度和饼干的饱腹度。输出可以吃饱的孩子的最大数量。
在这个样例中,我们可以给两个孩子喂 [1,2]、[1,3]、[2,3] 这三种组合的任意一种。

题解

因为饥饿度最小的孩子最容易吃饱,所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后,我们采取同样的策略,考虑剩下孩子里饥饿度最小的孩子,直到没有满足条件的饼干存在。
 
简而言之,这里的贪心策略是,给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现,因为我们需要获得大小关系,一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和饱腹度最小的饼干出发,计算有多少个对子可以满足条件。
注意 对数组或字符串排序是常见的操作,方便之后的大小比较。排序顺序默认是从小到大。
注意 在之后的讲解中,若我们谈论的是对连续空间的变量进行操作,我们并不会明确区分数组
和字符串,因为他们本质上都是在连续空间上的有序变量集合。一个字符串“abc”可以被看作一
个数组 [‘a’,‘b’,‘c’]。
 
 

题目描述

一群孩子站成一排,每一个孩子有自己的评分。现在需要给这些孩子发糖果,规则是如果一 个孩子的评分比自己身旁的一个孩子要高,那么这个孩子就必须得到比身旁孩子更多的糖果。所 有孩子至少要有一个糖果。求解最少需要多少个糖果。

输入输出样例

输入是一个数组,表示孩子的评分。输出是最少糖果的数量。
在这个样例中,最少的糖果分法是 [2,1,2]。

题解

存在比较关系的贪心策略并不一定需要排序。虽然这一道题也是运用贪心策略,但我们只需要简单的两次遍历即可:把所有孩子的糖果数初始化为 1;先从左往右遍历一遍,如果右边孩子的评分比左边的高,则右边孩子的糖果数更新为左边孩子的糖果数加 1;再从右往左遍历一遍,如果左边孩子的评分比右边的高,且左边孩子当前的糖果数不大于右边孩子的糖果数,则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历,分配的糖果就可以满足题目要求了。这里的贪心策略即为,在每次遍历中,只考虑并更新相邻一侧的大小关系。

在样例中,我们初始化糖果分配为 [1,1,1],第一次遍历更新后的结果为 [1,1,2],第二次遍历更新后的结果为 [2,1,2]。

 

区间问题

题目描述

给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

输入输出样例

输入是一个数组,包含多个长度固定为 2 的子数组,表示每个区间的开始和结尾。输出一个整数,表示需要移除的区间数量。
在这个样例中,我们可以移除区间 [1,3],使得剩余的区间 [[1,2], [2,4]] 互不重叠。

解题

求最少的移除区间个数,等价于尽量多保留不重叠的区间。在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。因此,我们采取的贪心策略为,优先保留结尾小且不相交的区间。
具体实现方法为,先把区间按照结尾的大小进行增序排序(利用 lambda 函数),每次选择结尾最小且和前一个选择的区间不重叠的区间。在样例中,排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略,首先初始化为区间
[1,2];由于 [1,3] 与 [1,2] 相交,我们跳过该区间;由于 [2,4] 与 [1,2] 不相交,我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]。

注意 需要根据实际情况判断按区间开头排序还是按区间结尾排序。

练习

基础难度

采取什么样的贪心策略,可以种植最多的花朵呢?
 

452. 用最少数量的箭引爆气球 - 力扣(LeetCode)
452. 用最少数量的箭引爆气球 - 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足  xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。 给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。   示例 1: 输入:points = [[10,16],[2,8],[1,6],[7,12]] 输出:2 解释:气球可以用2支箭来爆破: -在x = 6处射出箭,击破气球[2,8]和[1,6]。 -在x = 11处发射箭,击破气球[10,16]和[7,12]。 示例 2: 输入:points = [[1,2],[3,4],[5,6],[7,8]] 输出:4 解释:每个气球需要射出一支箭,总共需要4支箭。 示例 3: 输入:points = [[1,2],[2,3],[3,4],[4,5]] 输出:2 解释:气球可以用2支箭来爆破: - 在x = 2处发射箭,击破气球[1,2]和[2,3]。 - 在x = 4处射出箭,击破气球[3,4]和[4,5]。   提示: * 1 <= points.length <= 105 * points[i].length == 2 * -231 <= xstart < xend <= 231 - 1
452. 用最少数量的箭引爆气球 - 力扣(LeetCode)
这道题和题目 435 十分类似,但是稍有不同,具体是哪里不同呢?
 

为了满足你的贪心策略,是否需要一些预处理?
注意 在处理数组前,统计一遍信息(如频率、个数、第一次出现位置、最后一次出现位置等)可以使题目难度大幅降低。
 

股票交易题型里比较简单的题目,在不限制交易次数的情况下,怎样可以获得最大利润呢?

进阶难度

406. 根据身高重建队列 - 力扣(LeetCode)
406. 根据身高重建队列 - 假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。   示例 1: 输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释: 编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。 编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。 示例 2: 输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]   提示: * 1 <= people.length <= 2000 * 0 <= hi <= 106 * 0 <= ki < people.length * 题目数据确保队列可以被重建
406. 根据身高重建队列 - 力扣(LeetCode)
温馨提示,这道题可能同时需要排序和插入操作。
notion image
notion image
notion image
notion image
notion image
notion image
notion image
notion image
notion image

 
需要仔细思考你的贪心策略在各种情况下,是否仍然是最优解。
首先,看下面的几个测试用例,它们都因为数字 2 的出现,导致数组是非单调递增的。
例①: 4, 2, 5  例②: 1, 4, 2, 5 例③: 3, 4, 2, 5 当数组中出现 2 时,破坏了数组的单调递增。为了让数组有序,我们需要对 2 或者 4 进行调整:
第①个用例,我们可以 把 4 调小到 <= 2  或者 把 2 调大到 4、5 ,使数组有序。
notion image
第②个用例,我们可以 把 4 调小到 1、2  或者 把 2 调大到 4、5 ,使数组有序。
notion image
第③个用例,我们必须 把 2 调大到 4、5,才能使数组有序:我们不能把 4 调整为一个 <= 2 的数字,因为 4 前面的元素是 3.
notion image
三、归纳总结 当 nums[i] 破坏了数组的单调递增时,即 nums[i] < nums[i - 1]  时,为了让数组有序,我们发现一个规律(在上面三个例子中, nums[i] 都为 2, nums[i -1] 都为 4):
  1. 如例①的情况,当 i = 1 ,那么修改 num[i- 1] ,不要动 nums[i] ,因为nums[i]后面的元素是啥我们还不知道呢,少动它为妙。
  1. 如例②的情况,当 i > 1 时,我们应该优先考虑把 nums[i - 1] 调小到 >= nums[i - 2] 并且 <= nums[i]。同样尽量不去修改 nums[i] ,理由同上。
  1. 如例③的情况,当 i > 1 且 nums[i] < nums[i - 2] 时,我们无法调整 nums[i - 1] ,我们只能调整 nums[i] 到 nums[i - 1] 。
 

 
上一篇
《别笑!我是哲学家:笑出腹肌的28堂严肃哲学课》
下一篇
《小池大鱼》 ((日)小林一雅)

Comments
Loading...