这几道经典例题帮你轻松搞透贪心算法 6月17日 【今日算法】

贪心算法概念叙述

运用贪心算法求解问题时，会将问题分为若干个子问题，可以将其想象成俄罗斯套娃，利用贪心的原则从内向外依次求出当前子问题的最优解，也就是该算法不会直接从整体考虑问题，而是想要达到局部最优。只有内部的子问题求得最优解，才能继续解决包含该子问题的下一个子问题，所以前一个子问题的最优解会是下一个子问题最优解的一部分，重复这个操作直到堆叠出该问题的最优解。

贪心算法最关键的部分在于贪心策略的选择，贪心选择的意思是对于所求问题的整体最优解可以通过一系列的局部最优选择求得。而必须注意的是，贪心选择必须具备无后效性，也就是某个状态不会影响之前求得的局部最优解。

运动贪心算法解决相应问题时会比较简单和高效，省去了寻找全局最优解很多不必要的穷举操作，由于贪心算法问题并没有固定的贪心策略，所以唯一的难点就是找到带求解问题的贪心策略，但毕竟熟能生巧嘛，算法的基本思想总是固定不变的。

贪心算法求解步骤

1. 将问题分解为若干个子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

下面通过利用贪心算法解决四道LeetCode题目，加深一下对贪心算法思想的掌握，其中第一道为easy，其余三道为medium，会标注出相应的题号。

455.分发饼干

问题描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

• 你可以假设胃口值为正。
• 一个小朋友最多只能拥有一块饼干

这道题的思路主要包括两个点：

1. 尽量先满足胃口值小的孩子，因为这样的孩子容易满足。
2. 进行条件1时，尽可能选用尺寸小的，这样大尺寸饼干可以用来满足胃口值大的孩子。

这道题的贪心思想非常明显，就是要尽可能地满足更多的孩子，而胃口值小的孩子是容易满足的，反之胃口值大的孩子很难满足，所以在抉择上尽可能满足前者、饿着后者。

这个思想可以类比于赛马，我们假设赢或者平作为满足条件。如果A的3赢了B的1，那么剩下两匹的结果可能就是一平一负或者两负，那么此时至多才是1满足；而如果A的马和B的马都按照顺序比，则可以达到3平，那么此时可以达到3满足。

所以综上可以得到解题思路，首先需要将胃口值和饼干尺寸由小至大排序。设定一个计数器child，用来记得到满足的孩子个数，再维护一个饼干指针cookies。如果饼干尺寸可以满足孩子胃口值，即g[child]<=s[cookies]，就将child、cookies分别加一(向后移动一位)，否则只将cookies向后移动一位。因为孩子的胃口值是由小到大的，若不满足当前的胃口值更不会满足之后的。

时间复杂度：两次排序加一次循环，如果选择时间复杂度较优的排序方法，那么。

O(n)=O(n·log n)+O(n·log n)+O(n)=O(n·log n)。

55. 跳跃游戏

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

首先明确一下解题目标，若要能够到达最后一个位置，那么就需要最后一跳的最大距离加上该位置下标一定要大于等于数组长度，即nums[i]+i>=length(nums)，而当前元素又一定处于之前元素最远可以达到范围之内，这样层层嵌套不就是贪心算法思想中的子问题的形式嘛。

我们要从数组的第一个元素开始遍历，并且维护一个最远可以到达的位置(max_i)，当遍历到数组中的某一个位置i时，如果i在max_i范围之内，并且此时最远可以达到位置大于max_i，那么就通过i+nums[i]更新max_i，如果在遍历过程中max_i大于等于数组长度，则代表可以达到最后一个位置，反之不能。要注意的是，max_i既不是数组下标也不是数组中某个元素，而是二者的加和。

拿上面两个示例为例：

• 示例1：最开始下标为0的元素值为2，此时max_i=2，所以下标1、2都在max_i之内，当达到下标1时，此时max_i = 1+3 = 4，所以可以达到最后一个位置。
• 示例2：最开始下标为0的元素值为3，此时max_i=3，下标1、2、3在范围内，但在遍历这三个位置时会发现max_i=2+1=1+2=0+3总是等于3，而3<4，所以最后一个位置永远达不到。

时间复杂度：O(n)，一层循环。

435.无重叠区间

题目描述：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意：

1. 可以认为区间的终点总是大于它的起点。
2. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

本题的要求是“找到需要移出区间的最小数量”，换句话说就是要更多地保留集合中的区间，那么对于有重叠的区间，就应该尽可能删去跨度较大的区间。

这里我们根据区间的终点进行贪心选择，不是说起点不行，而是终点更好，那原因呢？因为如果每次选择的区间结尾越小，留给后面区间的空间自然就变多了，那么后面能留下的区间数量也就越多。用一句话概括就是每次都选择终点最小的，因为这一定是最优解的一部分，这不就是正是贪心思想的应用嘛。

解这道题时需要先将数组按照区间的终点进行排序，然后需要维护一个end指针，它代表当前集合中的最小终点，在遍历数组时，若当前元素的起点大于前一区间的终点，那么不重叠区间的计数器加一，更新end指针；反之则不做任何操作，最后区间总数减去不重叠区间即为需要移除区间的最小数量。

时间复杂度：一次排序加一次循环，O(n)=O(n·log n)+O(n)=O(n·log n)。 LeetCode中第452题：用最少数量的箭引爆气球与本题解法十分相似，大家可以类比本题的思路自己练习。

376. 摆动序列

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

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

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

示例1和示例3比较特殊，一个是完全摆动序列，另一个是完全升序序列，所以这里利用比较普通的示例2讲解，依据示例2中的数组可以大致绘制出一个元素分布图，如下：

其中橙色点就构成了一个摆动序列，所以橙色点的个数也是最终要输出的结果。可以看到[5,10,13,15]是一个连续递增的子序列，5处于17之后是符合题意的，所以一定将其保留，而对于[10,13,15]三个元素，只有保留15才可以形成摆动序列。

所以对于一段连续递增的子序列，只有保留这段子序列的首尾元素时，才能形成一个摆动序列，并且这也加大了尾部的后一个元素成为摆动序列的下一个元素的可能性。同理连续递减的子序列也做如上操作，比如图中的[15,10,5]。

解决这道题的关键就在于如何保留连续连续递增的子序列首尾元素，结合栈是一个很好的方法，但出栈入栈的条件是什么呢？我们维护一个状态值nowstate，他共有"up"和"down"两种取值，"up"表示该元素大于前一个元素，"dowm"表示该元素小于前一个元素。

从第二个元素开始遍历数组，因为第一个元素(下标为0)一定处于摆动序列内。若当前元素大于前一个元素且nowstate="up"，这就说明连续递增出现了，就需要从栈移除前一个元素。反之将nowstate更新为"up"，因为此时前一个nowstate="down"，另一种可能性同理。不论什么条件下都要做入栈操作，因为这里只靠条件过滤不符合的元素。

时间复杂度：O(n)，一层循环。

总结

从上面几道题中不难看出只要依据题意找出相应的贪心策略，解题就十分容易，并且代码也不复杂，但贪心选择的方法并不唯一，主要还是靠对算法的理解和解题的经验。贪心算法和动态规划是原理有些相似的两种算法，同一问题利用不同算法解题的思路、难易程度各不相同，不要相互混淆。

来源 | 奶糖猫

作者 | 奶糖猫