0455. Assign Cookies ==================== 题目信息 -------- :题号: 0455 :难度: Easy :主题: 孩子需求、饼干尺寸、一对一分配、最大满足人数 :原题: `LeetCode 0455 `_ :重点: 每个孩子最多一块饼干、每块饼干最多分给一个孩子、尺寸至少达到需求才满足、返回最大人数 题目重述 -------- 数组 ``g`` 表示孩子的胃口值,``g[i]`` 是满足第 ``i`` 个孩子所需的最小饼干尺寸;数组 ``s`` 表示现有饼干尺寸。每个孩子最多获得一块饼干,每块饼干也最多分配给一个孩子。 当分配的饼干尺寸 ``s[j] >= g[i]`` 时,该孩子被满足。返回通过最优分配能够满足的最多孩子数量。两个数组长度均位于 ``[1, 3 * 10^4]``,胃口值和饼干尺寸位于 ``[1, 2^31-1]``。 自建示例 -------- 部分孩子能够满足: .. code-block:: text 输入:g = [2,4,5],s = [1,2,5] 输出:2 解释:尺寸 2 的饼干满足胃口 2 的孩子,尺寸 5 的饼干满足胃口 4 或 5 的一个孩子;尺寸 1 无法满足剩余孩子。 没有足够大的饼干: .. code-block:: text 输入:g = [3,6],s = [1,2] 输出:0 解释:每块饼干都小于所有孩子的胃口值,因此无人被满足。 最小可行饼干优先匹配最小胃口 ---------------------------- 将孩子胃口和饼干尺寸都从小到大排序。当前最小饼干若连最小胃口都无法满足,就不可能满足任何更大的胃口,应直接丢弃;若它能够满足最小胃口,就把它分给该孩子,因为用更大的饼干替代只会浪费资源,不会增加可满足人数。 两个指针分别表示当前孩子和当前饼干。成功匹配时同时前进,否则只跳过过小的饼干,直到某一方耗尽。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findContentChildren(std::vector& g, std::vector& s) { std::sort(g.begin(), g.end()); std::sort(s.begin(), s.end()); int child = 0; for (int cookie : s) { if (child < static_cast(g.size()) && cookie >= g[child]) { ++child; } } return child; } }; 代码分析 -------- 当最小饼干不能满足当前最小胃口时,它对其余孩子也必然无用;当能够满足时,把它给当前最小胃口不会比给更大胃口少满足一个孩子,这构成交换论证。排序耗时 ``O(g log g + s log s)``,扫描耗时 ``O(g+s)``,额外空间复杂度为 ``O(1)``(不计排序实现的栈)。