贪心算法
概念：
顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。
举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。
分配类问题
题解：
因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。
简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。
至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int j=0;
int res = 0;
for(int i = 0;i<s.length;++i){
if(j>=g.length) break;
if(g[j]<=s[i]){
res++;
j++;
}
}
return res;
}135.分发糖果
题解：
做完了题目 455，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？虽然这一道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。
在样例中，我们初始化糖果分配为 [1,1,1]，第一次遍历更新后的结果为 [1,1,2]，第二次遍历更新后的结果为 [2,1,2]。
public int candy(int[] ratings) {
int len = ratings.length;
int res = len;
int[] targer=new int[len];
for(int i =len-2;i>=0;--i){
if(ratings[i]>ratings[i+1]&&targer[i]<=targer[i+1]){
res+=targer[i+1]+1-targer[i];
targer[i]=targer[i+1]+1;
}
}
for(int i =0;i<len-1;++i){
if(ratings[i]<ratings[i+1]&&targer[i]>=targer[i+1]){
res+=targer[i]+1-targer[i+1];
targer[i+1]=targer[i]+1;
}
}
return res;
}区间问题
435.无重叠区间
题解：
在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。
具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。
在样例中，排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于 [1,3] 与 [1,2] 相交，我们跳过该区间；由于 [2,4] 与 [1,2] 不相交，我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]
注意：需要根据实际情况判断按区间开头排序还是按区间结尾排序。
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (int[] o1,int[] o2)->{
return o1[1]-o2[1];
});
int res = 1;
int j = 0;
for(int i = 1;i<intervals.length;++i){
if(intervals[i][0]>=intervals[j][1]){
res++;
j=i;
}
}
return intervals.length-res;
}练习：
PS：以下题目均来自LeetCode
基础难度：
605.Can Place Flowers (Easy)
采取什么样的贪心策略，可以种植最多的花朵呢？452.Minimum Number of Arrows to Burst Balloons (Medium)
这道题和题目 435 十分类似，但是稍有不同，具体是哪里不同呢？763.Partition Labels (Medium)
为了满足你的贪心策略，是否需要一些预处理？
⬇
注意：在处理数组前，统计一遍信息（如频率、个数、第一次出现位置、最后一次出现位置等）可以使题目难度大幅降低。122.Best Time to Buy and Sell Stock II (Easy)
股票交易题型里比较简单的题目，在不限制交易次数的情况下，怎样可以获得最大利润呢？
进阶难度
406.Queue Reconstruction by Height (Medium)
温馨提示，这道题可能同时需要排序和插入操作。665.Non-decreasing Array (Easy)
需要仔细思考你的贪心策略在各种情况下，是否仍然是最优解。
