贪心算法：
贪心算法的主要思想是，在既定的策略下总是能在当前求出当前的最优解（局部最优解）而不是全局最优解。只是这样说可能比较难理解，下面从两道leetcode上的题目入手，来体会贪心算法。
1.分发饼干问题（力扣455题）
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
思路：那么应该怎么考虑这个问题呢？因为饥饿度最小的孩子是最容易吃饱的，所以我们先考虑这个小孩，我们应该把大于等于这个孩子饥饿度的，且是大小最小的饼干分给这个孩子。当这个孩子满足后，同样的方法，我们再考虑饥饿度第二小的孩子，以此类推。也就是说每次都满足当前饥饿度最小的小孩，找到局部最优解最终达到全局最优解。具体我们可以把两个数组都排序，从饥饿度最小以及饼干最小出发。
class Solution{
public int findContentChildren(int[] children,int [] cookies ){
int child = 0, cookie = 0;
Arrays.sort(children);
Arrays.sort(cookies);
while (child < children.length && cookie < cookies.length){
if (children[child] <= cookies[cookie]){
child++;
}
cookie++;
}
return child;
}
}
2.分发糖果问题（力扣135题）
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢
思路：这道题应该怎么考虑呢？因为题目要求每个孩子都必须会有一个糖果能分到，那不妨我们先让每个孩子都能分到一块糖果。我们先从左往右看，只有相邻的孩子才会互相影响糖果数量，也就是说从左往右遍历时，若发现右边的孩子比左边孩子的评分高，则右边孩子的数量要更新为比左边孩子的糖果数多一个(局部最优解)；第一轮遍历完成以后，我们再从右往左看，当左边的孩子比右边孩子评分高时，并且左边的孩子糖果数不大于右边的孩子，则左边孩子的糖果数更新为右边孩子的糖果数加一，两次遍历完成后即可得到全局最优解。
我自己写的比较麻烦，但比较容易理解，想看标准版的可以去看官方代码。
class Solution {
public int candy(int[] ratings) {
int res = ratings.length;
//分配糖果的数组，初始一人一个
int[] candis = new int[res];
for (int i = 0;i < candis.length;i++){
candis[i] = 1;
}
//从左往右遍历，若右边的孩子评分比左边的孩子高则右边孩子的糖果数+1
for (int i = 0;i < ratings.length - 1;i++){
if (ratings[i] < ratings[i + 1]){
candis[i + 1] = candis[i] + 1;
}
}
//从右往左遍历，若左边的孩子比右边的孩子评分高，并且左边的孩子不大于右边孩子的糖果
for (int i = ratings.length - 1;i > 0;i--){
if (ratings[i] < ratings[i - 1] && candis[i - 1] <= candis[i]){
candis[i - 1] = candis[i] + 1;
}
}
int sum = 0;
for (int i = 0; i < candis.length; i++)
{
sum = sum + candis[i];
}
return sum;
}
}
未经许可，禁止转载！
