0455. 分发饼干 #

标签：贪心、数组、双指针、排序
难度：简单

题目大意 #

描述：一位很棒的家长为孩子们分发饼干。对于每个孩子 i，都有一个胃口值 g[i]，即每个小孩希望得到饼干的最小尺寸值。对于每块饼干 j，都有一个尺寸值 s[j]。只有当 s[j] > g[i] 时，我们才能将饼干 j 分配给孩子 i。每个孩子最多只能给一块饼干。

现在给定代表所有孩子胃口值的数组 g 和代表所有饼干尺寸的数组 j。

要求：尽可能满足越多数量的孩子，并求出这个最大数值。

说明：

$1 \le g.length \le 3 * 10^4$。
$0 \le s.length \le 3 * 10^4$。
$1 \le g[i], s[j] \le 2^{31} - 1$。

示例：

示例 1：

1
2
3


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

示例 2：

1
2
3


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

解题思路 #

思路 1：贪心算法 #

为了尽可能的满⾜更多的⼩孩，而且一块饼干不能掰成两半，所以我们应该尽量让胃口小的孩子吃小块饼干，这样胃口大的孩子才有大块饼干吃。

所以，从贪心算法的角度来考虑，我们应该按照孩子的胃口从小到大对数组 g 进行排序，然后按照饼干的尺寸大小从小到大对数组 s 进行排序，并且对于每个孩子，应该选择满足这个孩子的胃口且尺寸最小的饼干。

下面我们使用贪心算法三步走的方法解决这道题。

转换问题：将原问题转变为，当胃口最小的孩子选择完满足这个孩子的胃口且尺寸最小的饼干之后，再解决剩下孩子的选择问题（子问题）。
贪心选择性质：对于当前孩子，用尺寸尽可能小的饼干满足这个孩子的胃口。
最优子结构性质：在上面的贪心策略下，当前孩子的贪心选择 + 剩下孩子的子问题最优解，就是全局最优解。也就是说在贪心选择的方案下，能够使得满足胃口的孩子数量达到最大。

使用贪心算法的代码解决步骤描述如下：

对数组 g、s 进行从小到大排序，使用变量 index_g 和 index_s 分别指向 g、s 初始位置，使用变量 res 保存结果，初始化为 0。
对比每个元素 g[index_g] 和 s[index_s]：
1. 如果 g[index_g] <= s[index_s]，说明当前饼干满足当前孩子胃口，则答案数量加 1，并且向右移动 index_g 和 index_s。
2. 如果 g[index_g] > s[index_s]，说明当前饼干无法满足当前孩子胃口，则向右移动 index_s，判断下一块饼干是否可以满足当前孩子胃口。
遍历完输出答案 res。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        index_g, index_s = 0, 0
        res = 0
        while index_g < len(g) and index_s < len(s):
            if g[index_g] <= s[index_s]:
                res += 1
                index_g += 1
                index_s += 1
            else:
                index_s += 1   

        return res

思路 1：复杂度分析 #

时间复杂度：$O(m \times \log m + n \times \log n)$，其中 $m$ 和 $n$ 分别是数组 $g$ 和 $s$ 的长度。
空间复杂度：$O(\log m + \log n)$。