题目描述
思路解析
一句话答案：LeetCode 455 分发饼干：孩子胃口和饼干尺寸各自排序，再用双指针从小往大匹配——小饼干先喂胃口最小的孩子，喂得饱就都前进、喂不饱就换更大饼干，时间 O(n log n)。
谁能喂饱谁，最多喂饱几个孩子
g[i] 是第 i 个孩子的胃口，s[j] 是第 j 块饼干的尺寸。一块饼干的尺寸只要不小于孩子的胃口，也就是 s[j] ≥ g[i]，就能把他喂饱，而且一块饼干只能给一个孩子。问用手里这些饼干，最多能喂饱几个孩子。题面例子 g=[1,2,3]、s=[1,1]，两块尺寸都是 1 的饼干顶多喂饱胃口 1 的那一个孩子，答案是 1。
把饼干挨个试着配孩子，会绕成什么样
手里有一堆饼干和一群孩子，一个直接的想法是给每个孩子去找一块还没用过、又刚好喂得饱他的饼干。可饼干配谁不配谁会互相牵制：一块饼干先给了这个孩子，另一个孩子可能就只能用更大的、甚至没得用；试遍所有搭配的数量会爆炸式膨胀，数一大就跑不动。想快下来，得先看出这些配对里藏着一个固定的先后次序。
为什么两边排好序、小饼干先喂小胃口
把孩子胃口 g 和饼干尺寸 s 都从小到大排好，再从最小的饼干、胃口最小的孩子看起。手里最小的这块饼干，如果连当前胃口最小的孩子都喂不饱，那它对后面胃口更大的孩子更没戏，直接丢掉不亏。如果它喂得饱，就把它用在这个胃口最小的孩子身上——把这块刚够的饼干省下来留给胃口更大的孩子，那个孩子未必吃得饱，反而白占一块。于是每一步都拿当前最小的饼干去满足当前最小的胃口，这种配了就不回头、每步都挑最不浪费的挑法就是贪心。为了同时盯住两边的进度，用两个指针 i、j 各自往前挪，一个跟着孩子、一个跟着饼干。
指针什么时候动，决定了答案对不对
两个指针都从开头出发，拿当前饼干和当前孩子比：s[j] ≥ g[i] 说明这块饼干喂得饱，满足数加一，孩子指针 i 往后挪去看下一个孩子；s[j] ＜ g[i] 说明连当前最小的胃口都够不着，这块饼干作废。不管配上没配上，饼干指针 j 每轮都往后走一格——配上了是这块饼干已经用掉，配不上是它太小、得翻到更大的那块。两个指针里任一个走到头就停，此刻的满足数就是要返回的答案。
g=[1,2,3]、s=[1,1] 手动喂一遍
两个数组本来就是升序，不用再排。先看开头：s[0]=1 ≥ g[0]=1，喂饱了胃口 1 的孩子，满足数变成 1，孩子指针和饼干指针各往后挪一格。再看 s[1]=1 ＜ g[1]=2，这块饼干喂不饱胃口 2 的孩子，只把饼干指针往后挪。这时饼干指针已经走到 2、等于饼干总数，饼干用完了，循环停下。满足数停在 1，正是这两块小饼干最多能喂饱的孩子数。
时间主要花在排序上，指针别挪反
整段代码的时间几乎全花在给两个数组排序上，各要 O(n log n)，后面双指针一趟扫过去只是线性的，合起来就是 O(n log n)；排序在原地做，除掉排序本身的开销只用两个指针和一个计数器，空间 O(1)。贪心成立的前提是先排序——忘了这步，从小到大匹配的地基就塌了，结论整个错。另外两个指针的挪法各有陷阱：饼干喂不饱当前孩子时顺手把孩子指针也挪走，会白白放弃一个本能被后面大饼干喂饱的孩子；配对成功却忘了让饼干指针 j 前进，同一块饼干会被重复算进满足数。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条「都排序后，小饼干优先去喂小胃口」，下面每一帧都在套它。
先把两个数组都从小到大排好。上面这行是排序后的饼干尺寸，指针 r 指向当前要考虑的饼干（从最小那块开始）。
饼干 s[0]=1 ≥ 孩子胃口 g[0]=1，能喂饱！这块饼干配给这个孩子（染绿）。满足人数 +1，孩子和饼干指针都前进，去看下一个孩子和下一块饼干。
饼干 s[1]=1 < 孩子胃口 g[1]=2，连当前胃口最小的孩子都喂不饱，这块饼干没用。扔掉它、指针 r 前进换更大的饼干，孩子不动（继续等能喂饱他的饼干）。
饼干 s[2]=1 < 孩子胃口 g[1]=2，连当前胃口最小的孩子都喂不饱，这块饼干没用。扔掉它、指针 r 前进换更大的饼干，孩子不动（继续等能喂饱他的饼干）。
饼干 s[3]=1 < 孩子胃口 g[1]=2，连当前胃口最小的孩子都喂不饱，这块饼干没用。扔掉它、指针 r 前进换更大的饼干，孩子不动（继续等能喂饱他的饼干）。
饼干 s[4]=2 ≥ 孩子胃口 g[1]=2，能喂饱！这块饼干配给这个孩子（染绿）。满足人数 +1，孩子和饼干指针都前进，去看下一个孩子和下一块饼干。
饼干 s[5]=2 < 孩子胃口 g[2]=3，连当前胃口最小的孩子都喂不饱，这块饼干没用。扔掉它、指针 r 前进换更大的饼干，孩子不动（继续等能喂饱他的饼干）。
饼干 s[6]=3 ≥ 孩子胃口 g[2]=3，能喂饱！这块饼干配给这个孩子（染绿）。满足人数 +1，孩子和饼干指针都前进，去看下一个孩子和下一块饼干。
饼干 s[7]=4 < 孩子胃口 g[3]=5，连当前胃口最小的孩子都喂不饱，这块饼干没用。扔掉它、指针 r 前进换更大的饼干，孩子不动（继续等能喂饱他的饼干）。
饼干 s[8]=5 ≥ 孩子胃口 g[3]=5，能喂饱！这块饼干配给这个孩子（染绿）。满足人数 +1，孩子和饼干指针都前进，去看下一个孩子和下一块饼干。
饼干 s[9]=6 < 孩子胃口 g[4]=7，连当前胃口最小的孩子都喂不饱，这块饼干没用。扔掉它、指针 r 前进换更大的饼干，孩子不动（继续等能喂饱他的饼干）。
饼干 s[10]=7 ≥ 孩子胃口 g[4]=7，能喂饱！这块饼干配给这个孩子（染绿）。满足人数 +1，孩子和饼干指针都前进，去看下一个孩子和下一块饼干。
扫到头了。绿色高亮的就是被用掉、各喂饱一个孩子的饼干，一共 5 块——也就是最多满足 5 个孩子。每个指针只走一遍，排序后 O(n log n)。
边界先想清：饼干不够大或不够多时，可能一个都满足不了。
两个高频追问，核心是「贪心选择的最优性证明」。
参考代码
def findContentChildren(g, s): g.sort() # 孩子胃口升序 s.sort() # 饼干尺寸升序 i = j = 0 # i:孩子指针 j:饼干指针 count = 0 while i < len(g) and j < len(s): if s[j] >= g[i]: # 这块饼干够喂饱当前孩子 count += 1 # 满足 +1 i += 1 # 看下一个孩子 j += 1 # 不管配没配上，这块饼干都翻过去 return count复杂度
- 时间：O(n log n)，主要花在给两个数组排序；双指针扫描只 O(n)
- 空间：O(1)，原地排序，只用两个指针和一个计数器（不计排序栈）
易错点
面试追问把动画讲成自己的话
追问为什么贪心「小饼干配小胃口」一定最优？
追问能不能反过来，从最大的饼干和最大的胃口开始配？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组拆分
LeetCode 561 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题