LeetCode 455. 分发饼干

2026-03-16 HGNULB 约 7 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 455. 分发饼干

题意分析

有一组孩子，第 i 个孩子的胃口值是 g[i]；另有一组饼干，第 j 块的尺寸是 s[j]。只有当 s[j] >= g[i] 时这块饼干才能让该孩子满足，且一块饼干最多给一个孩子、一个孩子最多拿一块。求最多能让多少个孩子满足。

约束信号有三处值得注意：两个数组给出时都是无序的，长度可以完全不同，而目标只是「被满足的孩子数量」这一个计数值，并不需要输出具体的分配方案。这说明任何能凑出同样数量的分配都算正确，解法有很大的重排自由度。

数值范围上，胃口和尺寸都是正整数且可以很大，所以不能开值域数组去做桶计数，只能依赖比较。

边界情况包括：孩子数为 0、饼干数为 0（答案都是 0）；所有饼干都比最小胃口还小（答案 0）；饼干数远多于孩子数（答案受孩子数封顶）；以及大量相等值同时出现在两个数组里，判据必须允许「尺寸恰好等于胃口」。

解法：排序 + 双指针

核心思路

暴力做法是枚举所有分配方式，或者把它当成二分图最大匹配来跑增广路：孩子和饼干各成一侧，s[j] >= g[i] 连边。这样做当然对，但匹配算法的代价在 $O(V\cdot E)$ 量级，对这题完全是杀鸡用牛刀。

瓶颈在于通用匹配算法没有利用「可满足关系由一条数值阈值决定」这个特殊结构：如果一块饼干能满足胃口为 5 的孩子，它必然也能满足胃口为 3 的孩子。也就是说边集是「阶梯状」的，而不是任意的。

顺着这个结构观察：把孩子按胃口升序、饼干按尺寸升序排好，然后同向扫描。面对当前最小胃口的孩子和当前最小的饼干，只有两种情况——饼干够大就直接配上（把最紧俏的资源用在最容易满足的需求上，不会让后面的孩子变差，因为被用掉的是最小的那块饼干）；饼干不够大，那它连最容易满足的孩子都满足不了，对剩下胃口更大的孩子更无能为力，只能永久丢弃。

由此得到扫描过程的不变量：任意时刻，下标小于 i 的孩子要么已经被满足、要么已被判定为「剩余饼干无法满足」；下标小于 j 的饼干要么已经用掉、要么已被判定为「对任何剩余孩子都太小」。两侧都不会有被冤枉丢弃的元素，因此扫描结束时的 count 就是最大值。

解题步骤

把 g 和 s 分别升序排序。排序是让上面那条「阶梯结构」显式成立的前提，没有有序性，「当前最小」这个概念就无从谈起。

令 i = 0 指向当前待满足的最小胃口孩子，j = 0 指向当前最小的待尝试饼干，count = 0 记录已满足人数。两个指针分别代表两侧「尚未定论」区间的起点。

当 s[j] >= g[i] 时匹配成功：count 加一，i 与 j 同时右移。孩子已被满足、饼干已被消耗，两侧的未定论区间同步收缩。

当 s[j] < g[i] 时只把 j 右移。此时孩子不能跳过——他是剩余孩子里最容易满足的，后面更大的饼干还有机会喂他；而这块饼干必须丢弃，因为它连最低门槛都过不去。

任一指针越界即退出循环并返回 count。孩子用完说明全部有定论，饼干用完说明剩下的孩子再也拿不到东西。

以 g = [1, 2, 3]、s = [1, 1] 走一遍：两数组本身已升序。初始 i = 0，j = 0，count = 0。第一轮，s[0] = 1 >= g[0] = 1，匹配成功，count = 1，i = 1，j = 1。第二轮，s[1] = 1 < g[1] = 2，这块饼干连胃口 2 都喂不饱，更喂不饱胃口 3，丢弃，j = 2，i 保持 1。此时 j = 2 等于 s 的长度，循环终止，返回 count = 1。

代码实现

class Solution {
    // 排序后优先用最小可行饼干满足胃口最小的孩子，不会影响后续更大胃口的孩子。
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        int count = 0;

        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }

        return count;
    }
}

func findContentChildren(g []int, s []int) int {
    // 排序后优先用最小可行饼干满足胃口最小的孩子，不会影响后续更大胃口的孩子。
    sort.Ints(g)
    sort.Ints(s)

    i, j := 0, 0
    count := 0

    for i < len(g) && j < len(s) {
        if s[j] >= g[i] {
            count++
            i++
            j++
        } else {
            j++
        }
    }

    return count
}

复杂度分析

时间复杂度：$O(n \log n + m \log m)$，其中 $n$、$m$ 分别是孩子数与饼干数。代价全部来自两次排序；之后的双指针扫描中每一轮至少让一个指针前进一格且指针从不回退，因此只有 $O(n + m)$。

空间复杂度：$O(\log n + \log m)$，只来自两次原地排序的递归栈（Java 的双轴快排、Go 的 pdqsort 都需要对数级栈深），算法自身只用了 i、j、count 三个整型变量。

关键点总结

贪心的正确性要靠交换论证支撑：取任意一个最优分配，若其中最小胃口的孩子没有配到最小的可行饼干，把两次分配对调后仍然合法且满足人数不变，反复对调即可变成本算法产出的解。

排序把「二维配对」压成「一维同向扫描」，这是所有「两组资源按阈值配对」题目的通用套路，值得从这题开始固化。

两个指针的推进条件是不对称的：成功时双双前进，失败时只丢弃资源侧。能说清这种不对称的来源，就说明真的理解了贪心而不是背下了模板。

循环出口条件用 && 而不是 ||：任一侧耗尽，剩下的元素就都有了定论，继续走只会越界。

面试视角：面试官几乎必然追问「凭什么贪心是对的」。答案不能停在「排序后从小到大配」，要给出「若当前饼干连最小胃口都满足不了，它对任何剩余孩子都无用，丢弃不损失最优解」这一步反证。

面试视角：可以主动点出这是二分图最大匹配的特例——一般图要跑匈牙利或 Hopcroft-Karp，而阈值型的边结构让它退化到排序复杂度。这类「识别出特殊结构」的表达最能体现算法素养。

易错点总结

错误写法：不排序就直接双指针扫描。用例 g = [2, 1]、s = [1, 2] → s[0] = 1 < g[0] = 2 丢弃第一块，s[1] = 2 >= 2 配上，返回 1，正确答案是 2。

错误写法：只对其中一个数组排序。用例 g = [1, 2]、s = [2, 1] 且只排 g → 第一轮 2 >= 1 得 1 分，第二轮 1 < 2 丢弃，返回 1，正确答案是 2。

错误写法：饼干太小时把孩子也一起跳过（i++ 与 j++ 同时执行）。用例 g = [1, 5]、s = [0, 1] → 第一轮丢掉孩子 1，第二轮 1 < 5 又丢掉孩子 5，返回 0，正确答案是 1。

错误写法：判据写成严格大于 s[j] > g[i]。用例 g = [1]、s = [1] → 尺寸恰好等于胃口却判为不满足，返回 0，正确答案是 1。

错误写法：匹配成功后只推进饼干指针，忘了推进孩子指针。用例 g = [1]、s = [1, 1] → 同一个孩子被两块饼干重复满足，返回 2，正确答案是 1。

错误写法：循环条件写成 i < g.length || j < s.length。用例 g = [1]、s = [1, 1] → 孩子耗尽后仍进入循环体访问 g[1]，下标越界抛异常。

错误写法：直接返回指针值当答案。用例 g = [2]、s = [1, 1] → 循环把 j 推到 2，返回 j 得 2，而实际一个孩子都没满足，正确答案是 0。

错误写法：认为「饼干数不少于孩子数就能全部满足」，直接返回 min(g.length, s.length)。用例 g = [10]、s = [1] → 返回 1，但这块饼干根本喂不饱，正确答案是 0。

相似题目

题目	难度	考察点
881. 救生艇	中等	同样排序后配对，但每条船最多载两人且有重量上限，目标是最小化船数
1679. K 和数对的最大数目	中等	配对判据是两数之和恰好等于 `k`，需要首尾双指针而非同向扫描
350. 两个数组的交集 II	简单	排序后同向扫描求交集，只有相等时双指针才同时前进，重复元素按次数保留
349. 两个数组的交集	简单	结果需要去重，扫描时要额外跳过与上一个答案相同的元素