一.方法介绍

贪心算法一般会对原数据进行一遍处理（如排序），使得一定规律变得更加明显，并根据这个规律来从局部最优扩展到全局最优。
保证每次操作都是局部最优的，从而使得最后得到的结果是全局最优的。不过一般是需要证明全局最优可以由局部最优推导出来。
在处理数组前，统计一遍信息（如频率、个数、第一次出现的位置、最后一次出现的位置等等），可以使题目难度大幅度降低。
贪心的地方有时不只一条，同时也需要分情况进行贪心讨论。

二.Leetcode题

45.跳跃游戏||

最佳的方法-贪心算法：维护一个当前边界end，一个在当前边界里面能到达的最远距离maxL，因为相当于从[0,end]到达[end,maxL]需要跨一步即可。所以在 i 遍历到当前边界end时，用maxL代替end，同时step++，继续循环。
自己的动态规划：dp[i]表示到达下标为i的位置所需的最小步数。然后用dp[j]+1（j:0-n-1）去更新 i :[j+1,j+nums[j]]下标位置的dp[i]
```
int jump(vector<int>& nums) {
     if (nums[0]==0||nums.size()==1)
         return 0;
     int i,j,step=0,maxL=0,end=0;
     for (i=0;i<nums.size()-1;i++) {
         maxL=max(maxL,nums[i]+i);
         if (i==end) {
             end=maxL;
             step++;
         }
     }
     return step;
}
```
122.买卖股票的最佳时机||
题目链接
——
解法一: 不怎么的贪心求解贪心求解，
只要第i天的卖出收益要比之前的较大的卖出收益小，则说明第i天的价格比之前的较大的价格小，将前面的卖出，仍然可以在后面去寻找 prices[i] minp 当前的最小价格, sumpre 保存前一次敲定的买卖的和 sumnow 保存这次买卖的较大和若prices[i]-minp=sumnow，则更新sumnow 初始化: minp=prices[0],sumpre=0,sumnow=0 输出 sumpre+sumnow
解法二:真正的贪心算法
只要prices[i]-prices[i-1]>0则就把股票卖出，始终保持上坡就卖贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。一次遍历就能实现，sum=sum+max(0,prices[i]-prices[i-1])

135.分发糖果-(分两次遍历，取两次遍历的较大值)

这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。
基本上局部的关系是123和321这两种情况，如果这两种情况能够有效处理好，就是比较好的方法。
贪心算法的左右规则：
左规则是从左往右，更新的是右边孩子；
右规则是从右往左，更新的是左边孩子；
先从左往右遍历一遍，若右边孩子的评分比左边孩子高，则右边孩子的糖果更新为左边孩子糖果数加1，所有学生满足左规则，分发糖果记录在left数组中再从右往左遍历一遍，若左边的孩子的评分比右边孩子高，则左边孩子的糖果更新为右边孩子糖果数加1，所有学生满足右规则，分发糖果记录在right数组中最后取left数组和right数组中对应位置的最大值，即可同时满足左规则和右规则。
证明我们取序列中的任意两点，A B 如果 A > B ,则按照左规则处理后，B不会比A多；按照右规则处理后，A一定比B多，那么A一定会被更新（变大），但L、R规则仍然成立：B不会比A多，A一定比B多；同理可讨论 A<B; 当 A == B，A、B的值无论如何更新，都不影响 L、R规则综上，取最大值后不影响某一规则的成立。

435.区间问题

题目链接
这题的贪心在于，在选择要保留的区间时，区间的结尾很重要，选择的区间的结尾越小，则余留给其他区间的空间就越大，则对于后面的而言，能保留更多的区间。

具体实现方法是：
先把区间按照结尾的大小进行增序排序，
然后每次去选择结尾小且和前一个选择的区间不重叠的区间。
对于排序，则可以结合sort()函数进行自定义排序。

sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
return a[1] < b[1];
});

在选择的时候，有如下几种选择的情况：
若新的区间的start大于等于上一次选定的区间的end，情况正常，之间加入
若新的区间的start小于上一次选定的区间的end，则说明有重叠，舍弃这个新的区间，

455.分发饼干

题目链接
从小到大把饼干给胃口从小到大排，并且首次满足的孩子，预留大尺寸饼干给胃口大的孩子。

605.种花问题

题目链接
贪心策略则是，当前位置如果能种花，则种上，当前位置如果不能种花，则检索下一个可能位置继续检索，大致的情况是以下几种，如果以下几种能根据这个贪心策略得到最优解，而这题的全局最优是由部分的局部最优构成的（一整串相当于被许多个1进行隔离），因此可以得到全局最优
1，0，0，1
1，0，0，0，1
1，0，0，0，0，1
0，1
0，0，1

665.非递减数列

题目链接
关注点就是如何处理不满足要求的特殊情况，也即nums[i]分情况讨论的贪心算法

若i=1，则可以直接修改nums[i-1],而不去修改nums[i],这样的话，对后面造成的影响最小，—贪心算法的所在。下面是论证，把nums[i-1]修改成小于等于nums[i]的值，这样如果后面的nums[i+1]>=nums[i]则满足条件，如果nums[i+1]<nums[i]，则即使修改nums[i]，也满足不了条件。
若i>1，则对于nums[i-2]、nums[i-1]、nums[i]，已知nums[i-2]和nums[i-1]是非递减的，

对于新的nums[i]，
若nums[i]>=nums[i-1]满足条件；
若nums[i]nums[i]，则只能去改动nums[i]，将其改成nums[i-1]。

贪心算法