分发饼干

难度: Easy

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

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

Submission

运行时间: 36 ms

内存: 17.5 MB

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        index = 0
        for i in range(len(s)):
            if index < len(g) and s[i] >= g[index]:
                index += 1
        return index

Explain

这个题解的思路是先将孩子的胃口值数组 g 和饼干尺寸数组 s 分别进行升序排序。然后使用两个指针 i 和 index，其中 i 用于遍历饼干数组，index 用于记录满足条件的孩子数量。在遍历饼干数组的过程中，如果当前饼干的尺寸大于等于 index 指向的孩子的胃口值，则说明可以满足该孩子，index 自增 1，继续判断下一个孩子。最后返回 index 的值，即为最多可以满足的孩子数量。

时间复杂度: O(max(nlogn, mlogm))

空间复杂度: O(1)

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()  # 对孩子胃口值数组进行升序排序
        s.sort()  # 对饼干尺寸数组进行升序排序
        index = 0  # 记录满足条件的孩子数量
        for i in range(len(s)):
            if index < len(g) and s[i] >= g[index]:  # 如果当前饼干尺寸满足当前孩子的胃口值
                index += 1  # 满足条件的孩子数量加 1
        return index  # 返回最多可以满足的孩子数量

Explore

排序孩子的胃口值和饼干的尺寸有助于优化分配过程。通过排序，可以确保我们总是尝试用最小的可用饼干来满足最小的胃口。这种贪心策略确保每次分配都是当前最优的选择，从而最大化总体满足孩子的数量。如果没有排序，我们将需要更多的比较操作来找到合适的饼干，从而增加算法的复杂度。

如果遇到一个饼干不足以满足当前最小胃口的孩子，这个饼干将被跳过，因为它不能被任何未满足的孩子所用。算法将继续检查下一个饼干，看它是否可以满足当前或更大胃口的孩子。这种情况不会影响算法的正确性，但会影响到饼干的利用效率，即可能会有一些饼干浪费。

如果胃口值数组g和饼干尺寸数组s长度极不平衡，算法的时间复杂度主要由较长数组的排序过程决定，即O(n log n)，其中n是较长数组的长度。在遍历过程中，只有较短的数组长度决定了实际的比较次数，因此遍历部分的时间复杂度为O(m)，其中m是较短数组的长度。总体而言，算法仍然高效，但在极端情况下（如一个数组远大于另一个），可能存在一些资源浪费。

题解描述中提到使用了两个指针可能是一个表述错误。实际代码中，`index` 作为唯一的指针记录了满足条件的孩子的数量，而遍历饼干数组使用的是普通的循环变量 `i`。这里 `i` 可以视为第二个“指针”，负责遍历饼干数组。因此，可以说使用了两个指针，但实际上只有一个指针（`index`）是用来追踪满足条件的孩子的数量的。