贪心算法 | LuckyFish的Blog

type

status

date

slug

summary

基本概念

根据代码随想录里说的，贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心算法一般分为如下四步：

将问题分解为若干个子问题

找出适合的贪心策略

求解每一个子问题的最优解

将局部最优解堆叠成全局最优解

贪心算法，看几个题目吧

分发饼干问题

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]

输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]

输出: 2

解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.

这里应该满足，胃口最大的那个优先被满足。所以我们得从后往前分析：

先对两个数列进行排序，然后遍历每个人，当大饼干能够满足相应的人的时候，饼干的指针index就减一。

火炉覆盖居民问题

长度为n的数组，表示一条线段，数组中每个数表示线段上等间距点的居民点居住情况，0为无人，1为有人，现在有x个火炉，放置在线段上，火炉的能升温的半径为d，求让居民点尽可能少地不受冻的情况下，受冻的居民点个数。

这里就是先把所有居民按照索引来寻找，也就是把[0 1 1]变成[1 2]这种。然后在这个地方安插火炉。看火炉能覆盖多少人。

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。