题目简介

LeetCode 455题"分发饼干"是贪心算法的经典应用：每个孩子有胃口值g[i]，每块饼干有大小s[j]，当s[j] >= g[i]时孩子能得到满足。目标是最大化满足的孩子数量。

核心矛盾在于有限饼干如何分配给不同胃口的孩子。例如：

• g = [1,2,3], s = [1,1]
   → 满足1个孩子
• g = [1,2], s = [1,2,3]
   → 满足2个孩子

解题思路

贪心策略

贪心算法通过局部最优选择达到全局最优，本题有两种策略：

• 优先满足小胃口孩子
  ：用最小饼干满足最小胃口，保留大饼干
• 优先满足大胃口孩子
  ：用最大饼干满足最大胃口，避免浪费

经证明第一种策略最优，因为小胃口孩子更容易满足，可减少饼干浪费。

算法步骤：

1. 对g和s升序排序
2. 双指针遍历：

   
   

• 饼干满足孩子时，双指针后移（计数+1）
• 不满足时，仅移动饼干指针
3. 遍历结束时返回计数

排序的必要性

排序确保按"从小到大"顺序匹配，避免大饼干浪费在小胃口孩子身上，是贪心策略的基础。

代码实现

import java.util.Arrays;class Solution {    public int findContentChildren(int[] g, int[] s) {        Arrays.sort(g);        Arrays.sort(s);
        int child = 0, cookie = 0;        while (child < g.length && cookie < s.length) {            if (g[child] <= s[cookie]) {                child++; // 满足计数+1            }            cookie++; // 无论是否满足，饼干指针后移        }        return child;    }}

代码解析：

• 排序阶段
  ：O(n log n + m log m)
• 双指针遍历
  ：O(n + m)
• 空间复杂度
  ：O(log n + log m)（排序栈空间）

复杂度分析

排序是主要时间开销，当n,m=10⁴时，排序占总时间的80%。

优化方案

1. 二分查找优化

当g远小于s时，用二分查找匹配饼干：

for (int m : g) {    int idx = Arrays.binarySearch(s, i, s.length, m);    if (idx < 0) idx = -idx - 1;    if (idx < s.length) { count++; i = idx + 1; }}

2. 提前终止

若剩余饼干均大于剩余孩子最大胃口：

if (s[cookie] >= g[g.length - 1]) return g.length;

测试用例演示

关键用例：

• 基本情况：g=[1,2,3], s=[1,1] → 1
• 完全满足：g=[1,2], s=[1,2,3] → 2
• 空数组：g=[], s=[1,2] → 0

类似题目推荐

总结

本题通过排序+双指针实现贪心策略，核心思想是"用最小资源满足最易满足需求"。解题关键：

1. 排序确保有序匹配
2. 双指针高效遍历
3. 边界情况处理（空数组、饼干不足）

掌握该题可延伸解决区间调度、资源分配等贪心问题，关键在于证明局部最优能导出全局最优。