什么是贪心算法？

贪心算法没有固定算法框架，它是一种解决问题的策略和思维，需要针对具体的问题来分析。贪心算法的一般步骤是

1. 分析问题，找到问题与子问题的隐藏的关系。
2. 将原问题拆分为多个子问题，找到所有子问题的最优解。
3. 将每一步的子问题最优解组合得到全局的最优解。

贪心算法在分步求解问题时，由于每一步都只考虑当前状态下最优选择，而不考虑是不是全局最优选择，即有可能是全局最优解也可能不是，所以贪心算法主要适用于当所有的局部最优选择最终能促成全局最优选择的情况。

下面看一个非常经典的零钱兑换问题。

情况一，有1元，2元，5元的人民币n张，怎么用最少数量的纸币凑18元呢？

很明显，只要每次都优先选择最大面额的纸币就能满足。

1. 选择5元，剩余18-5=13元。
2. 继续选择5元，剩余13-5=8元。
3. 继续选择5元，剩余8-5=3元。
4. 选择2元，剩余3-2=1元。
5. 选择1元，剩余1-1=0元，兑换完成。

这就是使用贪心算法来兑换零钱，每次都优先考虑当前状态最优的选择。但是并非所有情况都能适用贪心算法，比如下面这种情况。

情况二，有1元，5元，7元的人民币n张，怎么用最少数量的纸币凑18元呢？

使用贪心算法选择策略是

1. 选择7元，剩余18-7=11元。
2. 继续选择7元，剩余11-7=4元。
3. 选择1元，剩余4-1=3元。
4. 继续选择1元，剩余3-1=2元。
5. 继续选择1元，剩余2-1=1元。
6. 继续选择1元，剩余1-1=0元，兑换完成。

使用了6张纸币才兑换完成，很明显还有更好的方案，比如

1. 选择7元，剩余18-7=11元。
2. 选择5元，剩余11-5=6元。
3. 继续选择5元，剩余6-5=1元。
4. 选择1元，剩余1-1=0元，兑换完成。

只使用了4张纸币就完成了兑换，这是因为在第二次选择时，虽然7元是当前状态下的最优选择，但是并非全局的最优选择，对于这种，我们可以使用后面将要介绍的动态规划算法来解。

分发饼干

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

对每个孩子 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.

提示：

• 1 <= g.length <= 3 * 10⁴
• 0 <= s.length <= 3 * 10⁴
• 1 <= g[i], s[j] <= 2³¹ - 1

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。