跳到主要内容

LeetCode 455. 分发饼干

本节目标

将最小可行饼干优先分给胃口最小的孩子，最大化满足人数。

这是贪心选择与证明的资源匹配母题：饼干只有大小，孩子只有最低胃口。排序后让最小可行饼干服务最小胃口，才能把更大的资源留给更难满足的孩子。

题意与约束​

每个孩子最多领一块饼干，每块饼干也只能给一个孩子。g[i] 是孩子的最低胃口，s[j] 是饼干大小，返回最多能满足多少孩子。

直接思路与瓶颈​

枚举每块饼干给哪个孩子需要处理大量排列。即使使用回溯，某块饼干给不同孩子也会产生重叠状态，规模增大后不可用。

贪心模型与算法推导​

将胃口和饼干分别升序排序。指针 child 指向尚未满足的最小胃口；依次查看饼干，只有当当前饼干至少能满足 g[child] 时才分配并移动 child。不能满足最小胃口的饼干也不可能满足任何剩余孩子，应直接跳过。

正确性依据​

若一块可满足最小胃口的饼干被给了更大胃口的孩子，而最小胃口在某个最优方案中使用另一块不小于它的饼干，交换两块饼干后两个孩子仍满足，人数不变。因此总存在一个最优方案用当前最小可行饼干满足当前最小胃口；固定该选择后，剩余问题同构，归纳即可。

样例执行过程​

g=[1,2,3]、s=[1,1] 排序后不变。第一块 1 满足胃口 1，child=1；第二块 1<2，跳过，最终为 1。当 s=[] 时循环不执行，返回 0。

代码实现​

C++17
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int findContentChildren(vector<int> g, vector<int> s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int child = 0;
        for (int cookie : s) {
            if (child < static_cast<int>(g.size()) && cookie >= g[child]) {
                ++child;
            }
        }
        return child;
    }
};

复杂度分析​

排序为 O(m log m+n log n)，双指针扫描为 O(m+n)；排序原地进行，除排序实现外额外空间为 O(1)。

边界与易错点​

  • 饼干不足时返回已满足人数，不要继续访问孩子数组。
  • 当前饼干不够时只移动饼干指针，不能跳过孩子。
  • 题目求人数，不需要构造具体分配方案。

模式迁移​

“最小可行资源配最小需求”可迁移到船只载人、任务分配等单调匹配；若资源和需求不再可比较或有多维约束，简单排序通常失效。