华为 OD 训练营 · 题解精讲
LC455. 分发饼干
配套讲解：视频讲解 ↗
LC455. 分发饼干 视频地址：https://uha.xet.tech/s/42qqgV
题目描述
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干j 分配给孩子i，这个孩子会得到满足。 你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
题目解析
解题思路
本题采用贪心算法，核心策略是：优先满足胃口最小的孩子，并分配尺寸最小的可用饼干。这样能最大化饼干利用率，避免大饼干被小胃口孩子浪费。
具体做法是：先将孩子胃口数组 g 和饼干尺寸数组 s 分别按升序排序，然后用双指针 child 和 cookie 分别遍历两个数组。对于每块饼干，检查它是否能满足当前胃口最小的孩子（即 g[child]）。如果能满足，则 child 指针后移（表示这个孩子已满足）；无论是否满足，cookie 指针都后移（这块饼干已被使用或无法满足任何剩余孩子）。
关键步骤
1. 排序：对 g 和 s 升序排序，为贪心选择做准备。 2. 双指针遍历：
- 初始化
child = 0,cookie = 0 - 循环条件：
cookie < len(s)且child < len(g) - 每次判断
s[cookie] >= g[child]： - 若成立，
child += 1（孩子被满足） cookie += 1（无论是否满足，饼干都被消耗）
示意图（以 g = [1,2,3], s = [1,1] 为例）：
排序后：g = [1,2,3], s = [1,1]
初始：child=0, cookie=0
第1步：s[0]=1 >= g[0]=1 → child=1, cookie=1
第2步：s[1]=1 < g[1]=2 → child不变, cookie=2
循环结束，child=1复杂度分析
- 时间复杂度：
O(mlogm + nlogn)，其中m = len(g),n = len(s)。排序占主导，双指针遍历为O(m+n)。 - 空间复杂度：
O(logm + logn)，主要来自排序所需的栈空间（Python 的 Timsort 排序）。
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 分发饼干（ LeetCode 455 ）:https:#leetcode-cn.com/problems/assign-cookies/
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 1、将孩子们的胃口值按照从小到大的顺序排列
# 优先满足胃口小的孩子
g.sort()
# 2、将饼干按照从小到大的顺序排列
s.sort()
# child 代表 g 的下标，即表示有多少孩子的胃口得到满足
child = 0
# child 代表 s 的下标，即表示目前有多少饼干被使用了
cookie = 0
# 遍历所有的饼干
# 遍历过后，饼干只有两种状态
# 1、要么找到了需要这个饼干的孩子
# 2、要么剩下的孩子中，胃口值最低的孩子都大于这个饼干的值，那么这个饼干没人要
while cookie < len(s) and child < len(g) :
# 孩子的胃口得到了满足
if s[cookie] >= g[child] :
# 得到满足的孩子数量加 1
child += 1
# 查看下一个饼干能否找到需要的孩子
cookie += 1
# 最后返回孩子数量
return child
复杂度分析
时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogm+nlogn)，遍历数组的时间复杂度是 O(m+n)O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
空间复杂度：O(logm+logn)，其中 m 和 n 分别是数组 g 和 s 的长度。空间复杂度主要是排序的额外空间开销。