分发饼干 图解题解

谁能喂饱谁，最多喂饱几个孩子

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 前进，同一块饼干会被重复算进满足数。

Python

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

C++

int findContentChildren(vector<int>& g, vector<int>& s){
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0, count = 0;
    while(i < (int)g.size() && j < (int)s.size()){
        if(s[j] >= g[i]){    // 够喂饱
            count++; i++;    // 满足一个孩子
        }
        j++;                 // 饼干总是翻下一块
    }
    return count;
}

Java

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);              // 孩子胃口升序
    Arrays.sort(s);              // 饼干尺寸升序
    int i = 0, j = 0, count = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) {     // 这块饼干够喂饱当前孩子
            count++;            // 满足数 +1
            i++;                // 看下一个孩子
        }
        j++;                    // 无论是否配上，饼干都翻下一块
    }
    return count;
}