LeetCode 455这道题题库里名字叫“分发饼干”Assign Cookies算是很多刷题新手第一个接触到的贪心算法题目。先说它能解决什么问题有一群孩子每个孩子有一个胃口值有一堆饼干每块饼干有一个尺寸只有当饼干尺寸不小于孩子胃口时孩子才能吃饱目标是让吃饱的孩子数量尽可能多。代码很短核心思路几句话能讲完但这道题放在LeetCode热门100题里并不是没有道理——它把贪心算法的“排序双指针”套路浓缩成了一个非常干净的模板面试里既能考实现又能考证明。适合刚刷题不久、想建立贪心算法手感的人也适合准备面试、需要把“为什么会这么做”讲清楚的人。我第一次做这道题的时候第一反应是用暴力把所有分配组合都试一遍后来发现孩子和饼干数量上限都是三万暴力完全跑不动。这道题看似简单真正上手之后才会发现它的价值不在于“能AC”而在于它几乎完美地演示了贪心算法的整个思考流程怎么从直觉出发、怎么用排序简化问题、怎么写双指针、怎么证明局部最优就是全局最优。这篇文章就把这套流程从头到尾拆开讲一遍。1. 题目拆解与思路定位1.1 这道题到底在考什么先看题目给的原始信息。孩子数组g每个元素代表一个孩子的胃口值饼干数组s每个元素代表一块饼干的尺寸。每个孩子最多只能拿一块饼干一块饼干也只能给一个孩子只有当s[j] g[i]时饼干才能满足这个孩子。要求返回最多能满足多少个孩子。数据范围有几个关键点g的长度在 1 到 30000 之间s的长度在 0 到 30000 之间也就是说饼干可能一块都没有。g[i]和s[j]都是正整数最大能到接近 2 的 31 次方。这个数据范围直接决定了暴力解法不可行——如果两个数组长度都是 30000所有分配组合的数量是指数级的就算只枚举饼干分给哪个孩子也会直接爆炸。两个示例很典型。g [1,2,3]s [1,1]答案是 1因为只有一块尺寸为 1 的饼干能喂饱胃口为 1 的孩子另一块同样尺寸的饼干满足不了胃口为 2 的孩子。g [1,2]s [1,2,3]答案是 2因为两块尺寸分别为 1 和 2 的饼干刚够匹配两个孩子的胃口。这两个例子对应了两种常见情况一种是饼干不够一种是饼干富余两者都能被同一种策略覆盖。这道题本质上是一个资源分配问题有限资源饼干分配给多个需求方孩子每个需求方有一个最低接受标准胃口目标是最大化被满足的需求方数量。这种“资源池匹配需求”的模型在算法题里非常常见只是换了一层生活化的外衣。1.2 为什么第一反应是排序加双指针如果没有排序这道题看起来会很乱一块饼干可能满足这个孩子也可能满足那个孩子到底给谁最划算很容易陷入局部尝试。排序的作用是消除不确定性。把孩子的胃口从小到大排把饼干的尺寸也从小到大排问题就变成了两个有序数组的匹配。这个时候策略变得非常直观用当前最小的饼干去试当前最小的胃口。为什么这个策略成立你想一个胃口最小的孩子是对饼干要求最低的人。如果连他都没办法用当前最小的饼干满足那这块更小的饼干再怎么等也不会有其他人能接受所以它可以直接丢弃。反过来如果当前最小的饼干能满足这个最小的胃口那就立刻分配掉因为这块饼干对你来说是“刚好够用”而更大的饼干应该留给后面胃口更大的孩子。用一个生活化的类比来理解就好比家里来了一群朋友每个人的饭量不一样但你手上的食物大小也不一样。最稳妥的分配方式就是让饭量最小的人吃最小份的食物饭量最大的人吃最大份的。如果让一个饭量小的人拿走一大份后面饭量大的人可能就不够吃了整体满足的人数就会下降。双指针就是在这种排序后的结构上做线性扫描。一个指针指向孩子一个指针指向饼干能匹配就双双移动不能匹配就只看下一块更大的饼干。整个过程只遍历一遍非常高效。2. 核心代码实现与逐行解析2.1 C 版双指针写法先把最常见的 C 解法放出来这是 LeetCode 上很多人用的标准模板class Solution { public: int findContentChildren(vectorint g, vectorint s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i 0, j 0; while (i g.size() j s.size()) { if (s[j] g[i]) { i; j; } else { j; } } return i; } };这段代码看起来很短里面有几个细节值得说清楚。第一sort是必须的。如果不排序双指针完全失去意义因为你会基于一个没有顺序的数组做决策结果一定是错的。第二i是孩子指针j是饼干指针。当s[j] g[i]时说明当前这块饼干能满足当前这个孩子于是孩子指针和饼干指针都往前走相当于“这个孩子被喂饱了这块饼干也消耗掉了”。如果s[j] g[i]说明当前饼干连胃口最小的孩子都喂不饱那就只看下一块更大的饼干所以只有j。这里有一个不太好一眼看出来的技巧答案就直接用i来返回。因为i每满足一个孩子就自增一次它正好等于已经满足的孩子数量。一开始我写这道题的时候还单独定义了一个ans变量每次匹配成功就ans后来发现i本身就是计数完全没必要再开一个变量。当然用ans也不会错只是代码会冗余一点。循环终止条件用的是不是||。只要孩子遍历完了或者饼干遍历完了匹配过程就结束。这一点特别容易写错写成||就会越界访问数组。2.2 Python 与 Java 版本Python 版本的逻辑完全一样写法更简洁class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() i j 0 while i len(g) and j len(s): if s[j] g[i]: i 1 j 1 return i注意 Python 的List需要从typing导入LeetCode 环境里默认已经处理好了本地练习如果报错就先from typing import List。另外Python 里当s为空列表时len(s)是 0循环条件直接不成立返回 0不需要额外写空数组判断。Java 版本也很接近class Solution { 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; } }Java 的数组有length属性不是length()方法这个新手经常搞混。还有一个隐藏坑如果g或s是 null调用Arrays.sort会直接抛空指针但 LeetCode 的输入保证数组非 null所以本地测试时注意别传 null 就行。2.3 另一种思路从大胃口开始匹配正向思路是“小饼干给小胃口”反向思路则是“大饼干给大胃口”。先排序然后从数组尾部开始用最大的饼干去试胃口最大的孩子class Solution { public: int findContentChildren(vectorint g, vectorint s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i g.size() - 1; int j s.size() - 1; int ans 0; while (i 0 j 0) { if (s[j] g[i]) { ans; i--; j--; } else { i--; } } return ans; } };反向写法的逻辑是如果当前最大的饼干都满足不了当前胃口最大的孩子说明这块饼干喂谁都喂不饱可以直接丢弃如果满足就分配掉同时把两个指针往左移。两种写法最终结果一样只是视角不同。有两点要提醒。第一反向写法里要特别注意g.size() - 1这个初始值如果g为空g.size() - 1在无符号整数下会变成一个大数从而导致问题。不过这道题g的长度至少为 1所以还好。第二s可能为空此时j初始值是 -1循环条件j 0不成立直接返回 0没有问题。但如果用int j s.size() - 1在某些语言里s.size()是无符号类型直接减 1 会溢出成最大值这是一个非常隐蔽的坑在 C 里建议先用变量保存s.size()再转成 int或者直接写成短路形式判断 j 的初始值。实际做题时我推荐先掌握正向写法因为更符合直觉也更好向面试官解释。反向写法作为理解加深的补充即可。3. 复杂度分析、正确性证明与贪心判断3.1 时间与空间复杂度先看复杂度这道题的复杂度分析很简单但面试里很爱问。假设孩子数量为 n饼干数量为 m。步骤时间复杂度说明排序 gO(n log n)普通比较排序排序 sO(m log m)普通比较排序双指针扫描O(n m)每个元素最多被访问一次总时间O(n log n m log m)排序是主导额外空间O(1)排除排序递归栈空间这个复杂度在数据范围 30000 以内是非常轻松的排序是主要开销但即使两个数组都达到上限排序也就几十万次比较的级别运行时间完全可以忽略。如果你仔细抠细节C 标准库的sort在最坏情况下是 O(n log n)但实际是内省排序接近这个复杂度。3.2 为什么这个贪心是对的交换论证这一节是整道题最容易被人忽略、但最有价值的部分。很多人 AC 了这道题却说不清为什么贪心是对的导致面试被问到就卡壳。我建议把下面这个证明思路记住它属于“交换论证”的经典应用。先看当前胃口最小的孩子 x。假设存在一个最优解如果 x 本来就没被满足那么有两种可能。第一种是所有的饼干都被分配完了那就说明已经达到了最大可能满足人数x 没被满足是必然的不影响最优性。第二种是还有饼干没被分配但有一块饼干 b 被分给了另一个胃口更大的孩子 y。因为 x 的胃口小于等于 y 的胃口所以既然 b 能满足 yb 一定也能满足 x。这时候我们把 b 从 y 手里拿过来给 xy 变成了没被满足但满足总人数没有变少。也就是说我们总能调整出一个最优解其中 x 是被满足的。再考虑 x 和饼干 b 的尺寸选择。假设饼干 b 是当前所有饼干里能满足 x 的最小尺寸。如果某个最优解中 x 被一块更大的饼干 c 满足了那么我们把 c 换成 b把 b 原本的位置留给真正需要更大饼干的孩子或者干脆空着都不会让满足人数变少。因为 b 只是尺寸更小其他孩子可能更不需要它。经过这样两步交换我们证明了一定存在一个最优解包含“把能满足 x 的最小饼干给 x”这个决策。接下来把 x 和这块饼干从问题里移除剩下的孩子和饼干构成一个规模更小的相同问题。每一步都用同样的贪心策略每一步都不会把全局最优解排除掉所以最终结果就是全局最优。用大白话总结就是胃口最小的孩子是所有孩子里最好打发的。你用他能接受的最小代价把他打发掉剩下的资源只会更游刃有余不可能吃亏。这就是贪心成立的核心原因。3.3 怎么判断一道题能不能用贪心很多刷题新手看到贪心题就慌因为凭感觉“每一步取最优”听起来不严谨。我的判断标准很简单这一步做了某个局部最优选择之后会不会让后续所有可能选择都变差如果不会就大胆用贪心如果会大概率要改用动态规划。举一个典型的反例0-1 背包问题。假设你是想装价值最高的物品进一个固定容量的背包单位价值最高的东西不一定该先拿因为它可能体积很大挤掉了两件体积小但总价值更高的物品。在这个问题里局部最优单位价值最高会影响后续容量所以不能贪心只能 DP。再回来看分饼干这道题为什么它能贪心因为“用小饼干满足小胃口”这个操作不会剥夺任何其他孩子吃到大饼干的机会。孩子之间唯一的区别就是胃口大小饼干之间唯一的区别就是尺寸大小不存在“代价”和“收益”之间的复杂权衡。只要有一块饼干能让当前孩子吃饱分配出去就是稳赚不赔的。这就是分饼干和背包问题的本质差别。4. 实操易错点与常见坑排查4.1 写代码时最常踩的六个坑刷题群里经常有人在这道题上反复提交失败大部分都是下面几个原因我整理成一份速查表。错误类型错误写法正确写法后果忘记排序直接进入 while 循环sort两个数组双指针结果随机大概率出错循环条件用错逻辑运算符while (i n || j m)while (i n j m)数组越界或死循环比较符号写错if (s[j] g[i])if (s[j] g[i])相等情况漏算结果偏小返回变量写错返回j返回i或ans答案变成饼干消耗数量反向写法指针自减顺序混乱忘记写i--匹配成功i--, j--失败i--死循环或提前退出C 无符号整型减一int j s.size() - 1且s为空先转 int 再判断j变成超大数导致死循环这里重点说一下比较符号那条。题目说得很清楚“如果s[j] g[i]我们可以将这个饼干 j 分配给孩子 i”所以等号是合法的。如果写成那么胃口等于饼干尺寸的孩子会永远吃不到饼干答案肯定会偏小。别问我是怎么知道的我见过有人在这道题上 WA 了三次才发现是把这个符号看反了。还有就是“返回j”这个坑。有些同学把j当成“已经被使用的饼干数量”觉得最后只要返回它就行。但j在饼干不够匹配时会持续自增到数组末尾这时候j并不等于满足人数只有i或者一个单独维护的ans才是正确答案。4.2 相似题型与贪心套路对照分饼干属于“排序后按最值直接匹配”这一类题。这类题在 LeetCode 上有不少变体我列几个值得对照刷的题目难度贪心策略LeetCode 135 分发糖果Hard两次遍历从左到右维持右大于左的糖果增量从右到左维持左大于右LeetCode 435 无重叠区间Medium按区间结尾排序每次保留最早结束的区间LeetCode 452 用最少数量的箭引爆气球Medium按区间起点排序更新最小右边界LeetCode 55 跳跃游戏Medium维护最远可达位置贪心扩展现有覆盖范围LeetCode 122 买卖股票的最佳时机 IIMedium只要第二天价格更高就当天买入卖出局部利润累加等于全局最大这些题看起来差异很大核心思考路径其实一致排序或者明确顺序、找最小/最大/最早/最远等极值点、做局部决策、证明决策不会影响后续更优解。把这五道题连着刷完你对贪心的手感会明显提升。5. 扩展思考把分饼干思维用到工程场景5.1 如果规则改一改会怎样算法题最大的乐趣在于改规则。把 LeetCode 455 改几个条件就会得到完全不同的问题用来检验自己是不是真正理解了原题。第一个变体一块饼干可以切分成任意大小。这时候问题从“配对”变成了“总量匹配”。你只需要把饼干尺寸求和然后对孩子的胃口做前缀和用二分找最多能满足多少个孩子。复杂度可以做到 O(n log n m)但已经完全不是贪心双指针了因为饼干可分之后分配粒度变了。第二个变体每个孩子最多可以拿多块饼干但每块饼干不能拆分。这个情况下单个孩子可能需要组合多块饼干才能满足问题性质又变了可能需要优先队列或者更复杂的贪心甚至退化成背包问题。第三个变体要求输出具体的分配方案而不是只返回数量。这时候需要在匹配成功时记录match[i] j剪枝逻辑不变但代码要多维护一个映射。这些变体在面试里经常被拿来追问如果你能快速给出“规则变化会导致算法性质变化”的判断面试官会认为你对问题理解足够深。5.2 工程里的“分饼干”时刻很多人觉得算法题就是面试敲门砖工程上用不到。但“分饼干”这个模型在真实系统里确实能找到影子。最直接的是广告投放系统中的预算匹配广告主有预算上限好比胃口流量库存有不同出价要求好比饼干尺寸平台希望尽量多的广告主获得曝光机会本质上是一个“用有限库存匹配最多需求”的贪心问题。另一个例子是任务调度器一批任务有不同优先级要求一批空闲节点有不同的处理能力希望尽可能多的任务被执行策略同样是“小任务用小节点大任务用大节点”。还有云资源分配用户请求不同的实例规格可用资源池里有不同的规格包最大化满足用户数量时也是先排序再匹配。遇到这类系统设计题你完全可以引用“分饼干”的思考框架排序、双指针、局部最优不影响全局最优。这比背一堆设计模式更容易让面试官听懂你在说什么。我自己刷这道题时最大的收获其实不是代码而是“证明”这件事。一开始我只记住排序双指针的模板后来模拟面试被问到“为什么排序后从小的开始匹配就是最优”我愣了半天。后来认真做了一遍交换论证才发现所有贪心题的核心都是这个动作想清楚这一步的选择会不会让后面的选择变差如果不会就放心贪。现在我做任何一道新的贪心题第一件事就是问自己这句话。如果你刚开始刷 LeetCode别只满足于把这题 AC 掉花十分钟把证明吃透比你多刷十道简单题有用得多。
