没想到这就是贪心算法?用尽可能小的饼干去满足需求尽可能大的孩子。
啊这个,要怎么说。。。我想起以前遇到这种题目的时候都是不会的,甚至说我自己模拟出来都有点困难,它考虑的东西似乎有点多?……

其实就是因为它要进行排序,这样方便操作。但现在做做Leecode这种题目,就会发现自己总想尽可能地避免它,排序的空间复杂度最低是$O(nlogn)$,高的就是$O(n)$,所以就有点没想到(不敢用)。

知道要对数组进行排序后就容易了,根据贪心算法,我们要遍历饼干数组,把它里面的值与孩子的需求作比较,如果符合的话就匹配成功,然后继续遍历。
因为我们知道,对于排序后的饼干,如果小的饼干不能满足孩子,那么比它大的所有饼干都不能满足,所以只要从小到大遍历即可。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int max = 0;
        for(int i = 0, j = 0;i < s.length;i++){
            if(j < g.length && s[i] >= g[j]){
                j++;
                max++;
            }
        }
        return max;
    }
}

上面这写法有点个人,看到dl们的写法都像下面这样:

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){
            // 当前饼干能满足当前孩子,才到下一个孩子
            // 否则就换一个更大的饼干(即cookie++)
            // 直到所有的饼干(或者所有的孩子)都比较完成
            if(g[child] <= s[cookie]){
                child++;
            }
            cookie++;
        }
        return child;
    }
}

两种写法都通过了,但运行时间8ms,内存消耗40.5MB,由此看这两次排序还是挺耗时的。