贪心算法概念描述在使用贪心算法解决一个问题时，会将问题分解成若干个子问题，可以想象成一个俄罗斯套娃，使用由内而外贪婪原则为寻找当前子问题的最优解，即算法不直接从整体考虑问题，而是想求得局部最优。只有当内部子问题得到最优解时，下一个包含这个子问题的子问题才能求解，所以上一个子问题的最优解会成为下一个子问题最优解的一部分，重复这个操作直到堆叠这个问题的最优解。贪心算法最关键的部分是贪心策略的选择。贪心选择是指通过一系列的局部最优选择可以得到问题的整体最优解。必须注意的是贪心选择必须没有后遗症，即某个状态不会影响之前得到的局部最优解。运动贪心算法在求解相应问题时会相对简单高效，省去了很多不必要的穷举操作来寻找全局最优解。由于贪心算法问题没有固定的贪心策略，唯一的困难就是找到解决问题的解。贪心策略，但毕竟熟能生巧，算法的基本思想始终是固定的。贪心算法求解步骤将问题分解为若干个子问题，为每个子问题寻找合适的贪心策略求解最优解，并将局部最优解堆叠为全局最优解。接下来，我们将使用贪心算法解决四道LeetCode问题并进行深化。掌握贪心算法的思路，第一个简单，其他三个中等，对应的题号会标注出来。来源：LeetCode链接：https://leetcode-cn.com455.分发饼干问题描述：假设你是一位伟大的父母，想给你的孩子一些饼干。但是，每个孩子最多只能得到一个饼干。对于每个孩子i，都有一个食欲值gi，这是满足孩子食欲的最小尺寸的饼干；每个饼干j的大小为sj。如果sj>=gi，我们可以将这个cookiej分配给孩子i并且这个孩子会满意。你的目标是让尽可能多的孩子满意，输出这个最大值。注意：您可以假设胃口值为正。一个孩子最多只能吃一块饼干这个问题的思路主要包括两点：先尽量满足胃口小的孩子，因为这样的孩子很容易满足。在进行条件1的时候，尽量选择小尺寸的，这样可以用大尺寸的饼干来满足胃口大的孩子。这道题的贪心思想很明显，就是尽可能满足更多的孩子，胃口小的孩子容易满足，相反胃口大的孩子很难满足，所以尽量满足前者，渴望后者。这个想法可以比作赛马，我们假设获胜或平局是满足的条件。如果A的3胜B的1，那么剩下两匹马的结果可能是1平1负或者2负，那么此时最多满足1；而如果按顺序比较A的马和B的马，则可以达到3级，那么此时可以达到3满意。所以综上所述，我们可以得到解决问题的思路。首先，我们需要将胃口值和饼干大小从小到大排序。设置一个计数器子来记住满意的子数，并维护一个饼干指针cookies。如果饼干大小能满足孩子的胃口值，即g[child]<=s[cookies]，则分别给child和cookies加1（向后移动一位），否则只向后移动cookies一位。因为孩子的胃口值是从小到大的，如果现在的胃口值不满足，以后也不会满足。时间复杂度：两次排序加一次循环，如果选择时间复杂度更好的排序方式，则$O(n)=O(nlogn)+O(nlogn)+O(n)=O(nlogn)$55。跳跃游戏标题描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表您可以在该位置跳跃的最大长度。确定您是否可以到达最后一个位置。在解决问题之前，先明确解决问题的目标。如果要能够到达最后一个位置，那么就需要最后一次跳跃的最大距离加上位置的下标必须大于等于数组的长度，即nums[i]+i>=length(nums)，且当前元素必须在前一个元素的最远可达范围内。这种逐层嵌套的形式不就是贪心算法思想中的一个子问题吗？我们要从数组的第一个元素开始遍历，保持一个最远可达的位置（max_i），当遍历到数组中的某个位置i时，如果i在max_i的范围内，此时最远的如果position可以达到大于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.Non-overlappingintervals问题描述：给定一组区间，找出最少需要移除的区间数，使得剩余的区间不重叠。注意：可以认为一个区间的终点总是大于它的起点。区间[1,2]和[2,3]的边界相互“接触”，但不重叠。这道题的要求是“找到最少需要去掉的区间数”，换句话说就是在集合中保留更多的区间，那么对于重叠的区间，应该尽量删除跨度较大的区间。这里我们根据区间的终点进行贪心选择。不是起点不好，而是终点更好。是什么原因？因为如果每次选择的区间结束时间越小，后面留给后面区间的空间自然就越大，能留下的区间数就会更多。一句话概括就是每次都选择最小的终点，因为这一定是最优解的一部分，这不就是贪心思维的应用吗。在解决这个问题的时候，需要先按照区间的终点对数组进行排序，然后需要维护一个终点指针，代表当前集合中的最小终点。遍历数组时，如果当前元素的起点大于上一个区间的终点，则非重叠区间的计数器加1，并更新终点指针；否则，不执行任何操作。间隔总数减去非重叠间隔是要删除的最小间隔数。时间复杂度：一次排序加一次循环，$O(n)=O(nlogn)+O(n)=O(nlogn)$。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]是一个连续递增的子序列，17之后的5符合题意，所以必须保留，而对于[10,13的三个元素,15],只保留15个就形成了摆动序列。因此，对于一个不断增加的子序列，只有保留这个子序列的头尾元素，才能形成摆动序列，这也增加了最后一个元素成为摆动序列下一个元素的可能性。同理，不断减少的子序列也做上述操作，如图中的[15,10,5]。解决这个问题的关键在于如何保留不断增加的子序列的第一个和最后一个元素。结合入栈是个好方法，但是出栈入栈的条件是什么？我们维护一个状态值nowstate，它有“up”和“down”两个值。“up”表示该元素大于前一个元素，“dowm”表示该元素小于前一个元素。从第二个元素开始遍历数组，因为第一个元素（下标0）必须在摆动序列中。如果当前元素大于前一个元素且nowstate="up"，则表示发生了连续递增。您需要从堆栈中删除前一个元素。如果不是，则更新nowstate为“up”，因为此时之前的nowstate="down"，另一种可能性是一样的。不管是什么条件，push操作都要进行，因为这里只是用条件来过滤不符合要求的元素。时间复杂度：$O(n)$，一层循环。总结从上面的题中不难看出，只要根据题意找到对应的贪心策略，就很容易解题，而且代码也不复杂，但是方法贪心选择不是唯一的，主要看对算法的理解和解题经验。贪心算法和动态规划是两种原理有些相似的算法。不同的算法解决同一个问题的思路和难度是不同的，不要混淆。关注公众号【奶糖猫】第一时间获取更多精彩好文
