📃 题目描述

题目链接：455. 分发饼干 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

对每个孩子 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.

🔔 解题思路

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

另外，假设有尺寸为 6 和 7 两块饼干，如果有一个胃口为 5 的小孩，我们应该给他尺寸为 6 的饼干，而不是更大的尺寸 7

可以使用贪心策略，将小孩数组和饼干数组升序排序，然后从后往前遍历小孩数组和饼干数组

二刷的时候写了一个更通俗易懂的版本，注释写的很清楚啦~：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int res = 0;
        int si = s.length - 1;
        int gi = g.length - 1;
        while (si >= 0 && gi >= 0) {
            // 1. 当前饼干可以喂饱这个小孩
            if (s[si] >= g[gi]) {
                // 该饼干被消耗
                si --;
                // 该小孩被喂饱
                gi --;
                // 结果 + 1
                res ++;
            }
            // 2. 当前饼干无法喂饱这个小孩
            // 那么再往左遍历就更不能有饼干能够喂饱这个小孩了，即说明这个小孩无法被喂饱
            // 用这个饼干去尝试喂饱下一个胃口更小的小孩
            else {
                gi --;
            }
        }

        return res;
    }
}

---

下面是一刷的时候写的版本：先遍历小孩数组，先把大胃口的小孩喂饱

	class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null || g.length == 0 || s == null || s.length == 0) {
            return 0;
        }

        // 小孩数组降序排序
        Arrays.sort(g);
        // 饼干数组升序排序
        Arrays.sort(s);

        // 能够满足的小孩
        int count = 0;
        // 从后往前遍历小孩数组和饼干数组
        for (int i = g.length - 1; i >= 0; i --) {
            for (int j = s.length - 1; j >= 0; j --) {
                if (s[j] >= g[i]) {
                    count ++;
                    // 表示已经被吃掉了
                    s[j] = 0;
                    break;
                }
            }
                
        }

        return count;
    }
}

可以看出来，这个时间复杂度是 O(N^2)

事实上，我们可以优化下，用下标来控制饼干数组的遍历，而不是再起一个for循环，采用自减的方式，这也是常用的技巧，时间复杂度降到 O(N)

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null || g.length == 0 || s == null || s.length == 0) {
            return 0;
        }

        // 小孩数组降序排序
        Arrays.sort(g);
        // 饼干数组升序排序
        Arrays.sort(s);

        // 能够满足的小孩
        int count = 0;
        // 饼干数组的下标
        int index = s.length - 1;
        // 从后往前遍历小孩数组和饼干数组
        for (int i = g.length - 1; i >= 0; i --) {
        	if (index >= 0 && s[index] >= g[i]) {
                count ++;
                // index-- 表示已经被吃掉了
                index --;
            }
        }

        return count;
    }
}

当然了，上面的做法是大饼干先满足大胃口

我们也可以小饼干先满足小胃口，从前往后遍历，⭐ 注意这时需要先遍历饼干数组，先把小饼干喂出去

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null || g.length == 0 || s == null || s.length == 0) {
            return 0;
        }

        // 小孩数组降序排序
        Arrays.sort(g);
        // 饼干数组升序排序
        Arrays.sort(s);

        // 能够满足的小孩
        int count = 0;
        // 小孩数组的下标
        int index = 0;
        // 从前往后遍历饼干数组和小孩数组
        for (int i = 0; i < s.length; i ++) {
            if (index < g.length && s[i] >= g[index]) {
                index ++;
                count ++;
            }
        }

        return count;
    }
}

下面是我自己最开始做的时候一个想法，比较容易懂，但是其实没必要这么做

大饼干满足大胃口

从后往前遍历小孩数组（升序），假设当前遍历到的小孩胃口是 i，我们只要在饼干数组（升序）中找到第一个大于等于 i 的元素喂给这个小孩就可以了

事实上没必要在饼干数组（升序）中找到第一个大于等于 i 的元素喂给这个小孩，因为小孩数组已经升序了，假设他胃口是 6，你有 7 和 8 两个尺寸的饼干，给这个小孩哪个饼干都不重要了，因为后续的小孩的胃口不存在比 6 还大了。

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null || g.length == 0 || s == null || s.length == 0) {
            return 0;
        }

        // 小孩数组降序排序
        Arrays.sort(g);
        // 饼干数组升序排序
        Arrays.sort(s);

        // 能够满足的小孩
        int count = 0;
        // 从后往前遍历小孩数组，假设当前遍历到的小孩胃口是 i，我们只要在饼干数组（升序）中找到第一个大于等于 i 的元素喂给这个小孩就可
        for (int i = g.length - 1; i >= 0; i --) {
            for (int j = 0; j < s.length; j ++) {
                if (s[j] >= g[i]) {
                    // 将这个位置的饼干置为 0，表示已经被吃掉了
                    s[j] = 0;
                    count ++;
                    break;
                }
            }
        }

        return count;
    }
}