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]]。
注意 需要根据实际情况判断按区间开头排序还是按区间结尾排序。
练习
基础难度
采取什么样的贪心策略,可以种植最多的花朵呢?
这道题和题目 435 十分类似,但是稍有不同,具体是哪里不同呢?
为了满足你的贪心策略,是否需要一些预处理?
注意 在处理数组前,统计一遍信息(如频率、个数、第一次出现位置、最后一次出现位置等)可以使题目难度大幅降低。
股票交易题型里比较简单的题目,在不限制交易次数的情况下,怎样可以获得最大利润呢?
进阶难度
温馨提示,这道题可能同时需要排序和插入操作。









需要仔细思考你的贪心策略在各种情况下,是否仍然是最优解。
首先,看下面的几个测试用例,它们都因为数字 2 的出现,导致数组是非单调递增的。
例①: 4, 2, 5
例②: 1, 4, 2, 5
例③: 3, 4, 2, 5
当数组中出现 2 时,破坏了数组的单调递增。为了让数组有序,我们需要对 2 或者 4 进行调整:
第①个用例,我们可以 把 4 调小到 <= 2 或者 把 2 调大到 4、5 ,使数组有序。

第②个用例,我们可以 把 4 调小到 1、2 或者 把 2 调大到 4、5 ,使数组有序。

第③个用例,我们必须 把 2 调大到 4、5,才能使数组有序:我们不能把 4 调整为一个 <= 2 的数字,因为 4 前面的元素是 3.

三、归纳总结
当 nums[i] 破坏了数组的单调递增时,即 nums[i] < nums[i - 1] 时,为了让数组有序,我们发现一个规律(在上面三个例子中, nums[i] 都为 2, nums[i -1] 都为 4):
- 如例①的情况,当 i = 1 ,那么修改 num[i- 1] ,不要动 nums[i] ,因为nums[i]后面的元素是啥我们还不知道呢,少动它为妙。
- 如例②的情况,当 i > 1 时,我们应该优先考虑把 nums[i - 1] 调小到 >= nums[i - 2] 并且 <= nums[i]。同样尽量不去修改 nums[i] ,理由同上。
- 如例③的情况,当 i > 1 且 nums[i] < nums[i - 2] 时,我们无法调整 nums[i - 1] ,我们只能调整 nums[i] 到 nums[i - 1] 。
- Author:无敌宝宝男sp
- URL:http://www.wudibaobaoda.top/article/2824032f-33bf-8081-96db-f683e994b1e7
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!