分发饼干问题如何用贪心求解？（LeetCode 455）

简化版

有一群孩子各有胃口值 g[i]，一堆饼干各有尺寸 s[j]，一块饼干只能喂一个孩子，且饼干尺寸 ≥ 孩子胃口才能满足他。求最多能满足几个孩子。贪心策略：把胃口和饼干都排序，用「尽量小的饼干去喂胃口小的孩子」——小饼干别浪费在能被更小饼干满足的孩子身上。双指针一遍扫过，能喂就喂，统计满足人数。

详细版

int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);           // 孩子胃口升序
    Arrays.sort(s);           // 饼干尺寸升序
    int child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {   // 这块饼干够喂当前孩子
            child++;                    // 满足一个孩子
        }
        cookie++;                       // 无论是否喂出，这块饼干都用掉/跳过
    }
    return child;
}

策略：小饼干优先喂胃口小的孩子，把大饼干留给胃口大的，最大化满足人数。
两个指针：child 指向当前待满足的孩子（胃口最小的未满足者），cookie 遍历饼干。
喂不动就丢：若最小的饼干都喂不了当前最小胃口的孩子，这块饼干对谁都没用（后面孩子胃口只会更大），直接 cookie++ 跳过。
复杂度：排序 O(n log n + m log m)，扫描 O(n+m)。

完整版教学

一、题意与贪心直觉

题目本质是二分图最大匹配的一个特例，但因为「尺寸 ≥ 胃口」是一个简单的偏序关系，不需要真跑匹配算法，贪心就能拿到最优解。

先建立直觉：要满足尽可能多的孩子，就得让每块饼干都花在「刀刃」上——不浪费。 什么叫浪费？一块大饼干去喂一个胃口很小的孩子，就浪费了它「本可以喂胃口更大孩子」的能力。所以贪心方向有两种等价写法：

小饼干喂小胃口：从最小的饼干开始，喂给它能满足的、胃口最小的那个孩子。
大饼干喂大胃口：从胃口最大的孩子开始，用能满足他的最大饼干去喂。

两种都对，代码模板一是前者。

二、为什么排序是前提

不排序，你无法判断「谁是当前最小胃口的孩子」「谁是最小的饼干」。排序把无序的匹配问题变成了有序的线性扫描：胃口升序后，只要从左到右依次满足，被满足的一定是当前胃口最小的未满足孩子；饼干升序后，从小往大用，每块都优先服务它够得着的最小胃口。

三、双指针扫描的逻辑

两个指针 child（孩子）和 cookie（饼干）都从 0 开始：

若 s[cookie] >= g[child]：当前饼干能满足当前孩子 → 匹配成功，child++（下一个更大胃口的孩子），cookie++（这块饼干用掉）。
若 s[cookie] < g[child]：当前最小的饼干连当前最小胃口的孩子都喂不动 → 它对任何还没满足的孩子都没用（后面孩子胃口只增不减），果断丢弃，cookie++，child 不动。

循环到任一指针越界为止，child 的值就是被满足的孩子数。

四、贪心正确性证明（交换论证）

为什么「小饼干喂小胃口」不会漏掉更优解？用交换论证：

假设存在一个最优匹配方案 M，它没有把「最小的能满足孩子 A 的饼干 c」分给 A，而是把一块更大的饼干 c’ 给了 A，同时 c 给了另一个胃口更大的孩子 B（如果 c 根本没被用，那更能换）。因为 c ≥ g[A] 且方案里 c' ≥ g[A]、c ≤ c'，把 c 和 c’ 对调：A 拿 c（仍满足，因 c ≥ g[A]），B 拿 c’（仍满足，因 c' ≥ c ≥ g[B]）。对调后满足的孩子数不变，但更符合贪心选择。反复对调可把任意最优解「掰」成贪心解，说明贪心解的满足人数 = 最优——贪心正确。

五、易错点与变体

易错 1：cookie++ 的位置。模板里无论饼干是否喂出，cookie 每轮都 ++（喂出了要换下一块饼干；没喂出这块饼干也被证明无用要跳过）。而 child 只在成功喂出时才 ++。写成「只有喂出才 cookie++」会死循环。
易错 2：以为要精确匹配。饼干只需 ≥ 胃口，不是相等，别用哈希去找等值。
变体：一个孩子可分到多块饼干凑满胃口 → 就不是这道题了，会变成更复杂的分配问题；本题限定「一孩子最多一饼干」。
变体：求最小浪费/最大满意度加权 → 可能要 DP 或费用流，贪心不一定成立。

六、贪心选择为什么不会堵死未来

本题每一步选择是：按胃口和饼干尺寸升序，用当前最小能满足的饼干喂当前最小胃口孩子。

正确性不能只靠直觉，核心证明是：若某解用更大饼干满足该孩子，换成当前最小可用饼干仍满足，并给后面留下不小的资源。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：g=[1,2,3], s=[1,1] 只能满足 1 个；第二块 1 无法跨过胃口 2。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：目标是最大人数而非总满意度；无法满足当前最小胃口的饼干也不可能满足后续更大胃口。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：应该先满足胃口最大的孩子。 可能浪费大饼干；从最小需求匹配最小可行资源。
误区：小饼干不够当前孩子应保留。 后续孩子胃口更大，它永远无用。
误区：排序后是 O(n)。 还包含 O(n log n+m log m) 排序。
追问：为什么不会浪费解？ 交换后已满足人数不减且剩余资源更宽松。
追问：若饼干可拆分怎么办？ 问题模型改变，可能成为连续资源分配。
追问：若要最大化满意度总和？ 当前贪心目标不同，需重新建模。

九、加强记忆

分发饼干 = 排序 + 双指针贪心：胃口 g 和饼干 s 都升序，用小饼干喂小胃口（喂不动当前最小胃口的饼干对谁都没用，直接跳过），child 只在喂成功时前进、cookie 每轮都前进，最终 child 即最多满足人数。正确性靠交换论证（把大小饼干对调不减少满足数）。记住核心一句：别让大饼干浪费在小胃口上。

简化版

详细版