0455. Assign Cookies

题目信息

题号:

0455

难度:

Easy

主题:

孩子需求、饼干尺寸、一对一分配、最大满足人数

原题:

LeetCode 0455

重点:

每个孩子最多一块饼干、每块饼干最多分给一个孩子、尺寸至少达到需求才满足、返回最大人数

题目重述

数组 g 表示孩子的胃口值,g[i] 是满足第 i 个孩子所需的最小饼干尺寸;数组 s 表示现有饼干尺寸。每个孩子最多获得一块饼干,每块饼干也最多分配给一个孩子。

当分配的饼干尺寸 s[j] >= g[i] 时,该孩子被满足。返回通过最优分配能够满足的最多孩子数量。两个数组长度均位于 [1, 3 * 10^4],胃口值和饼干尺寸位于 [1, 2^31-1]。

自建示例

部分孩子能够满足:

输入:g = [2,4,5],s = [1,2,5]
输出:2
解释:尺寸 2 的饼干满足胃口 2 的孩子,尺寸 5 的饼干满足胃口 4 或 5 的一个孩子;尺寸 1 无法满足剩余孩子。

没有足够大的饼干:

输入:g = [3,6],s = [1,2]
输出:0
解释:每块饼干都小于所有孩子的胃口值,因此无人被满足。

最小可行饼干优先匹配最小胃口

将孩子胃口和饼干尺寸都从小到大排序。当前最小饼干若连最小胃口都无法满足,就不可能满足任何更大的胃口,应直接丢弃;若它能够满足最小胃口,就把它分给该孩子,因为用更大的饼干替代只会浪费资源,不会增加可满足人数。

两个指针分别表示当前孩子和当前饼干。成功匹配时同时前进,否则只跳过过小的饼干,直到某一方耗尽。

C++ 实现

class Solution {
public:
    int findContentChildren(std::vector<int>& g,
                            std::vector<int>& s) {
        std::sort(g.begin(), g.end());
        std::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(g log g + s log s),扫描耗时 O(g+s),额外空间复杂度为 ``O(1)``(不计排序实现的栈)。