LeetCode 455. 分发饼干——贪心正确性的交换论证方法

老张2026/4/30大约 21 分钟

LeetCode 455. 分发饼干——贪心正确性的交换论证方法

适读人群：Java中级工程师、备战大厂面试的同学 | 阅读时长：约25分钟 | 难度：简单偏中

开篇故事

记得我刚开始刷题的那段时间，贪心算法是我最害怕的一类题。不是因为代码写不出来，而是因为每次写完总觉得心里没底——凭什么这样贪就是对的？面试官一问"你怎么证明这个贪心策略是正确的"，我就哑巴了。

有一次参加内部技术分享，一个同事讲了一道分发饼干的题，说"很简单，排序之后双指针就行了"。我当时点头如鸡啄米，但心里一直在想：为什么排序之后双指针就一定是最优解？如果我用大饼干满足小胃口的孩子，腾出小饼干去满足其他孩子，难道不行吗？

这个疑问困扰了我很久，直到我真正搞清楚了"交换论证法"之后，才豁然开朗。贪心的难点从来不在于找到那个"贪"的方向，而在于严格证明这个方向是对的。今天这篇文章，我就以 LeetCode 455 为例，把交换论证法讲透，让你以后碰到贪心题，不再心虚。

其实回头看，贪心算法在工程项目里无处不在。我们团队做任务调度系统的时候，遇到过类似的问题：有一批任务（每个任务有最低资源需求），有一批可用的服务器（每个服务器有可用资源），怎么样把任务分配到服务器上，使得被成功调度的任务数量最多？这和分发饼干几乎是同一个问题。当时我自信满满地说"按照资源需求从小到大排序，然后用能满足的最小服务器去跑"，但被同事追问"你怎么证明这是最优的"，我又哑口无言了。

所以今天，我要彻底搞清楚这道题，不只是给你代码，而是给你一套可以迁移到任何贪心题的证明方法。

一、题目解析

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

输入输出示例：

输入：g = [1,2,3], s = [1,1]，输出：1（只有一块大小为1的饼干能满足胃口为1的孩子）
输入：g = [1,2], s = [1,2,3]，输出：2（饼干足够，两个孩子都可以被满足）

数据规模约束：

1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1（注意数值可以很大，涉及比较器时要防溢出）

问题本质分析： 这是一道经典的二分图最大匹配问题的特殊情形。孩子和饼干分别构成二分图的两侧，当且仅当 s[j] >= g[i] 时，饼干 j 和孩子 i 之间有边。我们要找这个二分图的最大匹配数。

暴力思路是枚举所有可能的孩子-饼干匹配方案，但这是指数级复杂度，面对 3×10^4 的数据规模根本无法通过。贪心的核心洞察是：我们应该用"刚好满足"的方式分配，避免浪费更大的饼干在小胃口的孩子上。

关键问题澄清： 什么叫"刚好满足"？对一个特定胃口的孩子，我们是用能满足他的最小饼干（不浪费资源），还是用尽量大的饼干（优先保障该孩子）？这两种策略哪种对全局更优？直觉上前者更好，但直觉是靠不住的，我们需要严格证明。

匹配的对称性： 这道题有一个有趣的对称性——"用最小饼干满足最小胃口的孩子"和"用最大饼干满足最大胃口的孩子"，这两种贪心方向其实等价，都能得到全局最优解。这个结论需要通过交换论证法来证明，是本文的重点。

二、解法一：暴力枚举匹配（超时，作为对照）

思路详解

暴力做法：枚举所有可能的孩子-饼干匹配方案，找出满足最多孩子的方案。由于每块饼干只能分配一次，且每个孩子最多分配一块，这本质上是一个带约束的枚举问题。

最朴素的实现是对每个孩子依次尝试分配每一块饼干，用回溯搜索所有方案，记录能满足最多孩子的方案。这种做法的搜索树有指数级大小，完全不适合实际使用，但它能帮助我们理解问题结构，为贪心优化提供对照。

通过观察暴力搜索树，我们可以发现一个规律：如果将孩子和饼干都按升序排列，那么最优匹配总是具有"不交叉"的性质——也就是说，在最优匹配中，胃口更大的孩子总是对应尺寸更大的饼干。这个观察是贪心策略的直觉来源。

代码实现

import java.util.Arrays;

public class Solution_Brute {
    private int maxSatisfied = 0;
    
    public int findContentChildren(int[] g, int[] s) {
        // 先排序，方便后续处理
        Arrays.sort(g);
        Arrays.sort(s);
        boolean[] usedCookie = new boolean[s.length];
        backtrack(g, s, usedCookie, 0, 0);
        return maxSatisfied;
    }
    
    private void backtrack(int[] g, int[] s, boolean[] used, 
                           int childIdx, int count) {
        if (childIdx == g.length) {
            maxSatisfied = Math.max(maxSatisfied, count);
            return;
        }
        // 当前孩子不分配饼干
        backtrack(g, s, used, childIdx + 1, count);
        // 尝试给当前孩子分配每一块未使用的饼干
        for (int j = 0; j < s.length; j++) {
            if (!used[j] && s[j] >= g[childIdx]) {
                used[j] = true;
                backtrack(g, s, used, childIdx + 1, count + 1);
                used[j] = false;
            }
        }
    }
}

复杂度分析

时间复杂度： O(n! × m) —— 每个孩子有 m 种饼干选择，且状态空间呈阶乘级增长，完全不可接受。
空间复杂度： O(n + m)，递归栈深度为孩子数量，visited 数组为 O(m)。

暴力解法的价值在于：它帮助我们明确了"最优匹配不交叉"这个性质，这正是贪心方向的来源——如果最优匹配中有交叉（大饼干给了小胃口孩子，小饼干给了大胃口孩子），我们可以交换，结果不变，因此总可以消除所有交叉得到不交叉的等价最优解。

三、解法二：双指针贪心（标准解法）

思路详解

核心贪心策略：用能满足孩子胃口的最小饼干去满足胃口最小的孩子。这被称为"小满足小"策略。

具体实现步骤如下：

第一步，将孩子胃口数组 g 和饼干尺寸数组 s 分别升序排序。排序之后，胃口最小的孩子排在最前面，尺寸最小的饼干也排在最前面。

第二步，用两个指针 i（指向当前待满足的孩子）和 j（指向当前待尝试的饼干）从小到大扫描。每次，我们检查当前饼干是否能满足当前孩子：如果 s[j] >= g[i]，当前饼干满足当前孩子，两个指针都向后移动，满足数加一；如果 s[j] < g[i]，当前饼干太小，连最小胃口的孩子都满足不了，这块饼干可以废弃，j++。

第三步，循环直到任一指针越界为止。最终 i 的值就是被满足的孩子数。

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

交换论证法是证明贪心算法正确性的主要工具，其核心思路是：假设最优解和贪心解在某一步不同，那么我们可以把最优解的那一步改成贪心的选择，结果不变甚至更好。通过这样的"替换"过程，可以逐步把最优解"变成"贪心解，从而说明贪心解也是最优解。

命题： 将能满足孩子 i（胃口为 g[i]）的最小饼干分配给孩子 i，这一策略不会使全局满足数变差。

完整证明过程：

设 OPT 是一个最优解（满足孩子数最多），GREEDY 是贪心解。我们对两者进行比较。

假设排序后的孩子依次是 c1, c2, ..., cn（胃口从小到大），饼干依次是 k1, k2, ..., km（尺寸从小到大）。

在 OPT 中，设孩子 c1（胃口最小）被分配了饼干 kp（其中 kp 是 OPT 中满足 c1 的饼干，尺寸为 s[p]，s[p] >= g[1]）。

在 GREEDY 中，c1 被分配了饼干 kq，其中 kq 是所有满足 c1 的饼干中尺寸最小的（s[q] 最小且 s[q] >= g[1]）。由于 kq 是最小满足饼干，s[q] <= s[p]。

现在我们将 OPT 中的 kp 替换为 kq（把 kp 分配给其他人，kq 分配给 c1）：

情况一： OPT 中没有其他孩子被 kq 满足（即 kq 在 OPT 中是"空闲"的）。直接将 c1 的饼干换成 kq，满足数不变，而 kp 现在空闲出来，可以用于满足更多孩子（kp >= kq，所以 kp 能满足的场景只多不少）。

情况二： OPT 中另一个孩子 ck（胃口为 g[k]）被 kq 满足。由于 kq 是从所有满足 c1 的饼干中选出的最小的，且 kp 也满足 c1（s[p] >= g[1]），并且 kp >= kq（因为 kq 最小），所以 s[p] >= s[q] >= g[1]。现在将 kp 给 ck，kq 给 c1，ck 是否还能被满足？g[k] <= s[q]（原本 kq 满足 ck），而 s[p] >= s[q]，所以 s[p] >= g[k]，ck 依然可以被满足。

结论： 无论哪种情况，将 OPT 中为 c1 选择的饼干换成 kq（最小满足饼干），满足数不减少。按此过程对 c2, c3, ... 依次做替换，最终将 OPT 完全"替换"成 GREEDY，满足数自始至终不减少。因此 GREEDY 的满足数 >= OPT 的满足数，而 OPT 是最优解，故 GREEDY 也是最优解。

反证法补充说明（更直观）：

假设贪心策略不是最优的，则存在某一步，贪心用了"恰好满足"的小饼干 j* 给孩子 i，但如果用了更大的饼干 j'（s[j'] > s[j*]），可以使总满足数更多。然而，j* 比 j' 小，用完 j* 后，j' 仍然可用于满足更大胃口的孩子；而用完 j' 后，j* 能满足的场景只减少不增加（因为 j' 浪费了更多"容量"，而 j* 本来可以保留给胃口更大的孩子）。这就与"贪心不是最优"的假设矛盾，故贪心策略正确。

代码实现

import java.util.Arrays;

public class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 分别对孩子胃口和饼干尺寸排序
        Arrays.sort(g);
        Arrays.sort(s);
        
        int i = 0; // 孩子指针，指向当前待满足的最小胃口孩子
        int j = 0; // 饼干指针，指向当前待尝试的最小尺寸饼干
        
        while (i < g.length && j < s.length) {
            // 当前饼干能满足当前孩子，两者都向前推进
            if (s[j] >= g[i]) {
                i++; // 孩子满足，移向下一个孩子
            }
            // 无论是否满足，饼干指针都向前
            // 满足后换下一块饼干，不满足说明太小需要更大的
            j++;
        }
        
        // i 就是满足的孩子数量
        return i;
    }
}

代码细节说明

关于 j++ 的位置，这是很多初学者容易出错的地方。j 在每次循环中必须无条件向前推进，原因如下：如果 s[j] >= g[i]，这块饼干被用来满足孩子 i，饼干已经消耗，下次必须用新饼干；如果 s[j] < g[i]，这块饼干太小，连最小的未满足孩子都满足不了，更小胃口的孩子已经被满足了（i 不后退），更大胃口的孩子也满足不了，这块饼干在这一轮彻底没用，j 必须前进。

复杂度分析

时间复杂度： O(n log n + m log m)，其中 n 是孩子数量，m 是饼干数量。排序占主导，双指针扫描是 O(n + m)。
空间复杂度： O(1)，不考虑排序内部栈空间。

四、解法三：反向贪心（大饼干优先策略）

思路详解

除了"小孩子小饼干"的策略外，还有另一种等价但视角不同的贪心：用最大的饼干优先满足胃口最大的孩子。这被称为"大满足大"策略。

这种策略的直觉是：大饼干是稀缺资源，我们应该把它给那些"非它不可"的孩子（胃口最大的），而不是浪费在小胃口的孩子身上。小饼干本来就能满足小胃口的孩子，不需要浪费大饼干。

从经济学的角度来说，这是一种"资源利用率最大化"的策略：每块饼干都用在了它能满足的最大胃口孩子身上，资源没有被"大材小用"。

正确性同样用交换论证法：

设最大饼干 j_max 在某最优解中满足了孩子 i（不是胃口最大的孩子），而我们的贪心要把 j_max 给胃口最大的孩子 i_max。

若 s[j_max] >= g[i_max]（最大饼干能满足最大胃口）：将 j_max 从孩子 i 换给孩子 i_max，孩子 i 用满足 g[i] 的其他饼干替代（因为 g[i] <= g[i_max] <= s[j_max]，且其他更小的饼干能满足 g[i]）。交换后满足数不变。

若 s[j_max] < g[i_max]（最大饼干都满足不了最大胃口）：说明没有饼干能满足孩子 i_max，跳过 i_max，对次大胃口的孩子重复此过程。

故两种策略（小满足小和大满足大）都正确，这两种方向实际上找的是同一组最优匹配对，只是遍历方向不同。

代码实现（从大到小匹配）

import java.util.Arrays;

public class Solution_Reverse {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int child = g.length - 1;  // 从最大胃口孩子开始
        int cookie = s.length - 1; // 从最大饼干开始
        int count = 0;
        
        while (child >= 0 && cookie >= 0) {
            if (s[cookie] >= g[child]) {
                // 当前最大饼干能满足当前最大胃口孩子
                count++;
                child--;  // 这个孩子已满足，移向次大胃口孩子
                cookie--; // 这块饼干已使用，移向次大饼干
            } else {
                // 最大饼干也满足不了当前孩子，当前孩子无法被满足
                child--; // 跳过这个孩子，它永远无法被满足
            }
        }
        
        return count;
    }
}

Mermaid 图：两种贪心方向的对比

复杂度分析

时间复杂度： O(n log n + m log m)，与解法二相同。
空间复杂度： O(1)。

深层理解： 两种贪心方向得到的答案完全相同，这不是巧合，而是因为它们本质上都在做同一件事——在升序排列的孩子和饼干之间找最大数量的"不交叉匹配"。在升序排序后，两种方向的双指针都是在贪婪地找出尽可能多的"g[i] <= s[j]"的不交叉匹配对。两种策略的等价性，是这道题最深刻的数学内涵。

五、举一反三

双指针匹配通用模板

// 贪心双指针匹配模板（升序排序后，小满足小）
public int greedyMatch(int[] needs, int[] resources) {
    Arrays.sort(needs);
    Arrays.sort(resources);
    int i = 0, j = 0;
    while (i < needs.length && j < resources.length) {
        if (resources[j] >= needs[i]) {
            i++; // 需求满足，移向下一个需求
        }
        j++; // 资源无论是否使用，都移向下一个
    }
    return i; // 满足的需求数
}

这个模板的核心思想是：资源指针永远向前推进，需求指针只在被满足时才向前推进。这保证了每块资源最多被使用一次，且总是以"能满足当前最小未满足需求的最小资源"的方式使用，从而实现了资源的最高效利用。

延伸：多维匹配的贪心

如果孩子有两个维度的胃口（比如既要考虑食物种类又要考虑数量），单纯的双指针就不够了，需要用更复杂的排序策略（比如 LeetCode 406 身高重建队列的多维排序贪心）。这类题目的共同特点是：先"固定"影响更大的那个维度，再在固定维度的基础上处理另一个维度。

六、踩坑实录

坑一：只对一个数组排序导致双指针逻辑混乱

我早期写这道题时，有时只对 g 排序忘了对 s 排序，有时只对 s 排序忘了对 g 排序。结果双指针的逻辑完全乱掉。原因是：双指针贪心的正确性建立在"两个数组都有序"的基础上，如果只有一个数组有序，"当前最小未满足需求"和"当前最小可用资源"就对不上，贪心策略就失效了。

举个反例：g = [3,1,2]（未排序），s = [1,2,3]（已排序）。双指针：s[0]=1 < g[0]=3，j++；s[1]=2 < g[0]=3，j++；s[2]=3 >= g[0]=3，i++；结果 i=1，但实际上三个孩子都能被满足，答案应该是 3。

教训： 贪心题涉及双数组双指针时，两个数组都必须排序，缺一不可。写完代码后第一件事是检查两个 Arrays.sort 都在那里。

坑二：循环条件写成了 || 导致越界

// 错误写法：提前结束
while (i < g.length || j < s.length) { ... }

// 正确写法：两个指针都有效才继续
while (i < g.length && j < s.length) { ... }

用 || 会导致一个指针越界后继续访问另一个数组，引发 ArrayIndexOutOfBoundsException。双指针问题中，任何一个数组遍历完，就代表没有更多匹配可能了，应该用 &&。

坑三：j++ 的位置写错导致死循环

我第一次写这道题时，错误地把 j++ 只放在了满足条件的分支里，在不满足的分支里忘了 j++，结果当 s[j] < g[i] 时，j 一直不前进，造成死循环。

// 错误写法（死循环）
while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) {
        i++;
        j++;
    }
    // 忘了写 else { j++; }，当 s[j] < g[i] 时死循环
}

// 正确写法（j 统一在循环末尾）
while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) i++;
    j++;
}

实际上，无论这块饼干满不满足当前孩子，它都需要"被消耗掉"——满足了孩子就被分配出去，满足不了就被跳过（因为如果连最小胃口的孩子都满足不了，后续更大胃口的孩子更不行）。

坑四：边界情况——饼干数组为空

题目约束 s.length 可以为 0（没有饼干）。这种情况下，while 循环的 j < s.length 条件一开始就不满足，循环直接不进入，返回 i=0，完全正确。但如果在 while 外有对 s[0] 的访问，就会越界。所以要保证所有对 s 的访问都在循环条件保护下。

坑五：误以为贪心只有一种方向

有些同学看完解法二之后，认为只有"小配小"这一种贪心，而没有意识到"大配大"同样正确。理解了交换论证法之后，你会发现两种方向都能找到同一组最优匹配，只是遍历顺序不同。这说明贪心策略并不是唯一的，关键是选一种容易实现且能证明正确的策略。

坑六：比较器的整数溢出

虽然本题的 Arrays.sort 是直接排序整数数组，Java 标准库会自动处理，但如果你用了自定义比较器，要注意 a - b 在 a 和 b 的绝对值很大时可能溢出（题目约束 g[i] 可以到 2^31 - 1）。安全写法是 Integer.compare(a, b) 而不是 a - b。

七、总结

分发饼干这道题的代码只有寥寥几行，但背后的思维含量却不少。今天我们重点讲了贪心正确性证明的核心方法——交换论证法（Exchange Argument）。

交换论证法的标准步骤：

第一步，假设存在一个最优解 OPT 与贪心解 GREEDY 在某个决策点不同。

第二步，找到两者第一个不同的决策，将 OPT 的那个决策改成贪心的选择（即"交换"）。

第三步，严格证明这次交换后，OPT 的质量不变（满足数不减少）。有时候交换会使 OPT 变得更好（但 OPT 已是最优，所以质量只能持平）。

第四步，重复上述过程，逐步将 OPT "变成" GREEDY，证明 GREEDY 与 OPT 质量相同，即 GREEDY 也是最优解。

贪心算法的两大核心要素：

一是找到"贪心选择属性"（Greedy Choice Property）：证明局部最优选择不会使全局最优解变差。这通常通过交换论证来实现。

二是找到"最优子结构"（Optimal Substructure）：证明大问题的最优解包含子问题的最优解。分发饼干中，满足了最小胃口的孩子后，剩余的孩子和饼干构成一个规模更小的相同问题，且原问题的最优解包含子问题的最优解。

这两个要素缺一不可。只有同时满足这两点，贪心算法才能保证正确性。以后遇到贪心题，不要只是"感觉这样贪是对的"，要能写出至少一两行交换论证的逻辑，这才是真正掌握了贪心算法的精髓。

解法	时间复杂度	空间复杂度	核心思想
暴力回溯	O(n! × m)	O(n+m)	枚举所有方案
小配小贪心（推荐）	O(n log n + m log m)	O(1)	最小满足资源匹配最小需求
大配大贪心	O(n log n + m log m)	O(1)	最大资源优先满足最大需求

两种贪心方向都是正确的，面试中推荐"小配小"（解法二），因为 if (s[j] >= g[i]) i++; 这一行代码非常直观地体现了"用最小可行饼干满足当前最小胃口孩子"的策略。

掌握了这道题，后面的区间调度、加油站、身高重建队列等贪心题，你都可以用交换论证法来验证自己的贪心策略是否正确，而不再依赖直觉或蒙运气。