LeetCode 455. 分发饼干
题目描述
题意分析
每个孩子有一个胃口值，每块饼干有一个尺寸。只有饼干尺寸不小于孩子的胃口，这个孩子才得到满足；每个孩子最多获得一块饼干，每块饼干也只能使用一次。返回最多能满足多少个孩子，不需要给出具体分配方案。
不能把多块小饼干合并给一个孩子，也不需要让所有孩子都得到饼干。相同胃口或相同尺寸仍对应不同的孩子、不同的饼干，都按出现次数参与分配；饼干数组允许为空。
解法：排序 + 双指针
核心思路
[!blue]
将胃口和饼干尺寸都升序排序。用
i指向尚未满足的最小胃口，用j指向尚未处理的最小饼干。优先给最容易满足的孩子寻找最小可行饼干，把更大的饼干留给后面要求更高的孩子。若
s[j] < g[i]，这块饼干连最小的剩余胃口都满足不了，更不可能满足后面的孩子，因此可以直接舍弃，只推进饼干指针。当前孩子仍可能被后续更大的饼干满足，不能一起跳过。若
s[j] >= g[i]，就把这块饼干分给当前孩子。这个选择不会减少最优人数：若某个最优方案给当前孩子用了更大饼干，可以交换成这块最小可行饼干，换出的较大饼干仍能承担原来这块饼干的任务；若最优方案没有满足当前孩子，把这块饼干改给他，也不会减少已经满足的总人数。因此每次成功匹配都可以保留在某个最优方案中，剩余部分仍是同样的问题。成功时两指针一起前进并计数，失败时只推进饼干指针。孩子或饼干任意一侧耗尽后，再也无法增加匹配数量，直接结束。
代码使用原地排序，会改变两个输入数组的顺序。排序只是为了确定安全的贪心次序，并不改变每个孩子和每块饼干只能使用一次的限制。
解题步骤
- 将胃口数组
g和饼干数组s分别升序排序。- 初始化两个指针和满足人数为零。
- 当前饼干足够大时，满足当前孩子，人数加一并同时推进两侧。
- 当前饼干太小时，只推进饼干指针。
- 任一指针到末尾时返回已满足人数。
代码实现
class Solution {
// 排序后优先用最小可行饼干满足胃口最小的孩子，不会影响后续更大胃口的孩子。
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
int j = 0;
int count = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
// 最小可行饼干满足当前最小胃口，两侧同时前进
count++;
i++;
j++;
} else {
// 饼干太小，只跳过饼干，当前孩子仍可由后续饼干满足
j++;
}
}
return count;
}
}
import "sort"
func findContentChildren(g []int, s []int) int {
// 排序后优先用最小可行饼干满足胃口最小的孩子，不会影响后续更大胃口的孩子。
sort.Ints(g)
sort.Ints(s)
i, j := 0, 0
count := 0
for i < len(g) && j < len(s) {
if s[j] >= g[i] {
// 最小可行饼干满足当前最小胃口，两侧同时前进
count++
i++
j++
} else {
// 饼干太小，只跳过饼干，当前孩子仍可由后续饼干满足
j++
}
}
return count
}
复杂度分析
- 时间复杂度：$O(n\log(n + 1) + m\log(m + 1))$，
n为孩子数，m为饼干数。排序后的双指针扫描为 $O(n + m)$。- 空间复杂度：扫描部分为 $O(1)$；整体还需计入 Java、Go 标准库排序实现使用的辅助空间，不能因为扫描未建新数组就将总空间一概视为常数。
关键点总结
[!green]
- 最小可行饼干满足最小剩余胃口，可以通过交换论证保留最优人数。
- 太小的饼干对所有剩余孩子都无用，可以舍弃；孩子本身仍需等待。
- 两指针之前的对象都已处理，匹配后同步推进保证不会重复使用。
易错点总结
[!yellow]
- 未排序就按当前次序分配，可能先用掉较大的饼干，让后面的更大胃口无法满足。
- 饼干太小时同时推进孩子，会漏掉仍可由后续饼干满足的人。
- 比较条件写成严格大于，会拒绝尺寸刚好等于胃口的有效匹配。
- 将多个饼干尺寸相加后匹配一个孩子，改变了每人最多一块的题目规则。
- 忽略排序对输入顺序的修改，误以为函数仅仅读取原数组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 870. 优势洗牌 | 中等 | 同样匹配两组大小需求，本题让最小足够饼干满足最小胃口，原题还需把无法获胜的值分配给对方。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！