455 分发饼干

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

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

题解

观察题目，我们会下意识的想到要保证g[i]能够恰好被满足就行。所以我们从胃口小的开始，然后遍历饼干，从小饼干开始遍历，这样会求出最大满足的孩子数量。

那么遍历的时候需要从哪一个开始遍历呢？

假设我们从胃口g开始遍历，对于s来说，我们需要找到能满足g[i]的s[index]。所以不仅仅是外层循环，内层也要不断地找到能match住s[i]的g[index]

javascript

let sIndex = 0
let count = 0
for(let i=0;i<g.length;i++) {
    //先找到能够满足g[i] 的 sIndex
    while(sIndex < s.length && s[sIndex] < g[i]) {
        sIndex++
    }
    //如果已经越界，那么就退出
    if(sIndex >= s.length) {
        break;
    }
    count++
    //当前满足一个孩子了，这个sIndex用了，需要往后移位
    sIndex++
}

但是如果我们从s开始遍历，就会好很多。为什么？因为我们是从饼干里挑合适的给孩子，如果合适了就加一，不合适就不加一，直到所有的饼干遍历完了，剩下的孩子就没有饼干分。

举例来说： g = [3,9,11] s = [1,2,4,5,6,7,9,10]

如果我们从g开始，就需要上面那个流程。但是如果我们从s开始，我们只需统计满足的数字即可。

javascript

let gIndex = 0
for(let i=0;i<s.length;i++) {
    if(gIndex < g.length && g[gIndex] <= s[i]) {
        gIndex++
    }
}

所以我们整体代码是

javascript

var findContentChildren = function (g, s) {
    g.sort((a, b) => a - b)
    s.sort((a, b) => a - b)

    let index = 0
    for (let i = 0; i < s.length; i++) {
        if(index < g.length && g[index] <= s[i]) {
            index++
        }
    }

    return index
}

总结，这里我们并没有来证明这里贪心算法一定是对的，但是事实上是可以证明的，但是证明的过程也是很花时间的。详细证明可以看这里：https://leetcode.cn/problems/assign-cookies/solutions/534281/fen-fa-bing-gan-by-leetcode-solution-50se/ 我们在做题的过程中并不需要来证明，只需要不能举出反例以及符合直觉就行了。这也是贪心算法难点所在。

455 分发饼干 ​

题解 ​

455 分发饼干

题解