455. 分发饼干（Assign Cookies）
频次 ★★★ · 难度 🟢 · 高频：字节
题目
每个孩子有胃口值 g[i]，每块饼干有尺寸 s[j]。如果 s[j] >= g[i]，这块饼干可以满足孩子 i。每个孩子最多一块饼干，求最多能满足多少个孩子。
示例：
输入: g = [1,2,3], s = [1,1]
输出: 1 （只有尺寸 1 的饼干能满足胃口 1 的孩子）
输入: g = [1,2], s = [1,2,3]
输出: 2
思路
贪心（小饼干优先满足小胃口孩子）：将孩子胃口和饼干尺寸分别排序，双指针遍历。用最小的饼干去满足最小的胃口，不浪费大饼干。这是贪心入门的经典题，核心思想是”局部最优 → 全局最优”。
代码
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) { // 当前饼干能满足当前孩子
i++; // 孩子满足，指针后移
}
j++; // 饼干无论是否满足都要后移（用过了或太小了）
}
return i;
}复杂度
- 时间：O(n log n + m log m) —— 排序
- 空间：O(1)
边界条件
- 没有饼干（s 为空）：返回 0
- 没有孩子（g 为空）：返回 0
- 所有饼干都小于最小胃口：返回 0
- 饼干足够大满足所有孩子：返回 g.length
变式
易错点
- 饼干指针 j 总是后移：无论是否满足孩子，饼干用过（或太小）都不能再用，所以 j++ 在 if 外面
- 先排序再贪心：不排序无法保证”小饼干配小胃口”的局部最优策略
面试追问
- 为什么这种贪心策略是正确的？ 如果一块饼干能满足一个孩子，用它去满足胃口最小的孩子是最优的——因为大胃口的孩子有更多饼干可选，小胃口的孩子只有少数饼干能满足
- 如果反过来，大饼干优先满足大胃口孩子呢？ 同样正确，对称策略。两种都行，本质一样