一、题目描述分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例1

输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。

示例2

输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.

二、思路分析熟悉笔者的应该了解之前分享了多篇的动态规划算法了，此题如果通过动态规划来解决的话有个痛点--二维什么叫二维呢？之前我们在动态规划中机器人寻址也是二维的。为什么那里可以通过动态规划来实现呢？首先我们来回顾下机器人走路图示 ， 我们当前状态(i,j)和上面两种状态是有关联的且这种关联我们是可以通过方程进行描述的但是将同样的布局放置到分饼干中就有点麻烦了。首先我们当前状态(i,j)并不一定来自源（i-1,j）或者（i,j-1）。我们这样理解下：当孩子g固定时，s块饼干可能可以分配给m个孩子(m<g) 。 随着饼干的增加并不确定m会不会增加。因为饼干的大小是未知的。所以动态规划在分饼干中就有点捉襟见肘了。针对本题贪心算法就很合适 。 贪心算法的本质就是局部最优来实现问题的解决贪心算法和动态规划不同的是前者是通过正向推进来实现问题解决的。在动态规划中是需要通过前一状态来决定当前状态的。而贪心算法是不考虑之前状态的。只考虑当前自己状态。总结一句话就是贪心算法只保证自己当前问题的解决不靠别人

image-20210524142935535

贪心分析既然采用贪心算法，那么我们就得确定贪心的策略这点和动归确定转移方程是一样的。首先我们需要将孩子和饼干进行排序排序规则按胃口值从小到大。因为我们需要知道有多少孩子能够被满足所以我们已孩子为主体进行扩展。我们在g[i]是需要在s中找到大于当前孩子胃口值的饼干的最小值。为什么需要最小值呢？上图中我们将满足情况的最小的饼干分配给当前孩子，那么下一个饼干也满足条件可以继续分配给下一个孩子但是如果我们不是将满足条件的最小饼干分配出去，最坏的情况就会出现前一个饼干无法满足下一个孩子三、AC 代码初版基于上面的分析我们可以给出如下的代码。下面就是将排序后的饼干最小满足情况分配给当前孩子这样能尽可能多地满足更多的孩子里面有些边界情况我们需要判断下，因为是已孩子为主体循环的不会产生数组越界的情况。但是饼干数组会出现数组越界，下面的if判断就是防止数组越界

public int findContentChildren(int[] g, int[] s) {    if (s.length == 0) {        return 0;    }    Arrays.sort(g);    Arrays.sort(s);    int sIndex = 0;    int total = 0;    for (int i = 0; i < g.length; i++) {        if (sIndex >= s.length) {            return total;        }        while (g[i] > s[sIndex]) {            sIndex++;            if (sIndex >= s.length) {                return total;            }        }        sIndex++;        total++;    }    return total;}

public int findContentChildren(int[] g, int[] s) {    Arrays.sort(g);    Arrays.sort(s);    int total = 0;    for (int i = 0; i < g.length; i++) {        for (int j = i; j < s.length; j++) {            if (s[j] >= g[i]) {                //为了下次在被别的孩子比较，这里置为-1，就不会分配给任何孩子                s[j] = -1;                total++;                break;            }        }    }    return total;}

public int findContentChildren(int[] g, int[] s) {    if (s.length == 0) {        return 0;    }    Arrays.sort(g);    Arrays.sort(s);    int total = 0;    int startPos = 0;    for (int i = 0; i < g.length; i++) {        for (int j = startPos; j < s.length; j++) {            if (s[j] >= g[i]) {                total++;                startPos=j+1;                break;            }        }    }    return total;}

创作不易，希望能得到你的点赞、关注

原文链接：