LC455. 分发饼干

题目描述

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

题目解析

题目在说什么

想象一下，你是一个幼儿园老师，手里有一堆饼干，每个饼干大小不一样。孩子们排着队，每个孩子都有一个“胃口值”——比如有的孩子胃口小，吃一个小饼干就饱了；有的孩子胃口大，需要大饼干才能饱。规则是：每个孩子最多只能拿一块饼干，而且饼干必须大于等于孩子的胃口值，孩子才会满意。你的目标是：让尽可能多的孩子满意。

比如，孩子胃口是 [1, 2, 3]，饼干大小是 [1, 1]。你只有两块小饼干，只能让一个胃口为 1 的孩子满意（因为第二个饼干也是 1，但第二个孩子胃口是 2，不够）。所以答案是 1。

这个问题其实就是：给你两个数组，一个代表孩子的胃口，一个代表饼干大小，你要找出最多能喂饱几个孩子。

思路是怎么来的

新手可能会想：那是不是应该把最大的饼干给胃口最大的孩子？或者随便分？但这样可能浪费饼干。比如，你有一块大饼干和一块小饼干，如果先把大饼干给了胃口小的孩子，那胃口大的孩子就没得吃了，可能只能喂饱一个。但如果你把小饼干给胃口小的孩子，大饼干给胃口大的孩子，就能喂饱两个。

所以，关键是要“物尽其用”——让每块饼干都发挥最大价值，不要浪费。怎么做到呢？一个很自然的想法是：先满足胃口小的孩子，因为他们容易满足，用最小的饼干就能搞定。这样就能把大饼干留给胃口大的孩子，避免“大材小用”。

这个思路就是“贪心算法”——每次只考虑当前最优的选择（先满足最容易满足的孩子），最终得到全局最优解。就像生活中，你会先把容易解决的小事做完，再集中精力处理大事。

具体做法是： 1. 把孩子的胃口从小到大排序。 2. 把饼干的大小也从小到大排序。 3. 然后从最小的饼干开始，试着喂给当前胃口最小的孩子。如果这块饼干够大，就喂给他，然后看下一个孩子；如果不够大，就换下一块更大的饼干试试。

这样，每块饼干都不会被浪费，而且每个孩子都尽量用最小的合适饼干去满足。

代码逐步拆解

我们来看参考代码，一步步解释它在干什么。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 1、排序：把孩子的胃口从小到大排列
        Arrays.sort(g);
        // 2、排序：把饼干的大小从小到大排列
        Arrays.sort(s);

        // child 表示当前正在考虑第几个孩子（从0开始）
        int child = 0;
        // cookie 表示当前正在看第几块饼干（从0开始）
        int cookie = 0;

        // 只要还有饼干没试过，并且还有孩子没被满足，就继续
        while(cookie < s.length && child < g.length){
            // 如果当前饼干能喂饱当前孩子（饼干大小 >= 孩子胃口）
            if(s[cookie] >= g[child]){
                // 这个孩子被满足了，我们去看下一个孩子
                child++;
            }
            // 不管这块饼干能不能喂饱当前孩子，它都被用过了，去看下一块饼干
            cookie++;
        }

        // 最后，child 就是被满足的孩子数量
        return child;
    }
}

关键点解释：

• 为什么先排序？因为排序后，我们才能保证“最小的饼干”和“最饿的孩子”对应，这样贪心策略才能执行。如果不排序，你无法知道哪个孩子胃口最小，哪个饼干最小。
• 为什么 child 和 cookie 都从0开始？因为排序后，索引0就是最小的胃口和最小的饼干。
• 为什么 if 里满足条件才 child++？因为只有孩子被喂饱了，才轮到下一个孩子。如果饼干不够大，这个孩子还饿着，我们继续看下一块更大的饼干能不能喂饱他。