什么是贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如有一堆不同数额的钞票，每次只能拿一张，怎么拿能取得最大数额的钞票。
- 方法：将钞票从大到小进行排序，每次都拿走当前堆里最大面额的钞票，即可在指定拿取次数中获得最大数额的钞票。
- 例如：[100, 100, 50, 20, 50, 1, 10]
  - 排序后为：[100, 100, 50, 50, 20, 10, 1]
  - 依次取数组中的最大值进行累加
  - 取完指定次数后，累加值即为最优解
- 在这个过程中，每次取最大面额的钞票为局部最优，通过每次获得局部最优得到的结果即为全局最优。

注意：贪心算法并没有固定套路，也没有固定策略，贪心算法有时候就是常识的推导，所以认为本应该这么做！

小题一道-分发饼干

题目

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干j 分配给孩子i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例1

输入: g = [1,2,3], s = [1,1]

输出: 1

解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

示例2

输入: g = [1,2], s = [1,2,3]

输出: 2

解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.

《代码随想录》算法公开课

力扣题目链接

思路

首先，每个孩子只能获得一块饼干，大尺寸的饼干能满足对于饼干需求小于等于该尺寸的孩子
为了减少饼干的浪费，这里我们优先考虑将大尺寸的饼干给到胃口大的孩子
即此处的局部最优便是，将大尺寸的饼干分给胃口大的孩子，全局最优便是尽量喂饱更多孩子

代码实现

优先考虑胃口，先喂饱大胃口的孩子

class Solution {
    //优先考虑胃口，先喂饱大胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);//对两个数组进行升序排序
        Arrays.sort(s);
        //count统计被喂饱的孩子
        int count = 0;
        //饼干尺寸从大到小进行与孩子胃口匹配
        int start = s.length - 1;
        // 遍历胃口
        for (int index = g.length - 1; index >= 0; index--) {
            //start >= 0为了防止数组越界错误
            //当饼干尺寸满足孩子时，将饼干分给g[index],然后饼干向更小的尺寸移动，孩子也向胃口更小的移动，如果孩子胃口大于饼干尺寸，则无法满足该孩子，直接向胃口小的孩子移动
            if(start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

优先考虑饼干，小饼干先喂饱小胃口

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = 0;
        int count = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}