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)``(不计排序实现的栈)。