Easy

题目描述

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

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

示例 1：

输入：g = [1,2,3], s = [1,1]
输出：1
解释：你有 3 个孩子和 2 块饼干。3 个孩子的贪心因子分别是 1、2、3。
虽然你有 2 块饼干，由于它们的尺寸都是 1，你只能让贪心因子是 1 的孩子满足。
所以你应该输出 1。

示例 2：

输入：g = [1,2], s = [1,2,3]
输出：2
解释：你有 2 个孩子和 3 块饼干。2 个孩子的贪心因子分别是 1、2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

提示：

  • 1 <= g.length <= 3 * 10^4
  • 0 <= s.length <= 3 * 10^4
  • 1 <= g[i], s[j] <= 2^31 - 1

注意： 这个问题与 2410. 玩家和训练师的最大匹配数 相同。

解题思路

这是一道经典的贪心算法题目。要最大化满足的孩子数量，我们应该采用贪心策略：对于每个孩子，尽量给他们能满足其需求的最小饼干。

核心思路如下：

  1. 排序：将孩子的贪心因子数组 g 和饼干尺寸数组 s 都按升序排序
  2. 双指针遍历：使用两个指针分别指向孩子数组和饼干数组的当前位置
  3. 贪心匹配：
    • 如果当前饼干能满足当前孩子（s[j] >= g[i]），则匹配成功，满足孩子数加1，两个指针都向前移动
    • 如果当前饼干不能满足当前孩子（s[j] < g[i]），则只移动饼干指针，寻找更大的饼干

这种贪心策略的正确性在于：如果一个较小的饼干能满足贪心因子较大的孩子，那么它也一定能满足贪心因子较小的孩子。为了最大化满足的孩子数量，我们应该把小饼干优先分给贪心因子小的孩子，这样能避免浪费。

时间复杂度主要由排序决定，为 O(n log n + m log m)，其中 n 和 m 分别是孩子和饼干的数量。

代码实现

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        
        int i = 0, j = 0, count = 0;
        while (i < g.size() && j < s.size()) {
            if (s[j] >= g[i]) {
                count++;
                i++;
            }
            j++;
        }
        
        return count;
    }
};

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

public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        Array.Sort(g);
        Array.Sort(s);
        
        int i = 0, j = 0, count = 0;
        while (i < g.Length && j < s.Length) {
            if (s[j] >= g[i]) {
                count++;
                i++;
            }
            j++;
        }
        
        return count;
    }
}

var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    
    let i = 0, j = 0, count = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) {
            count++;
            i++;
        }
        j++;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n + m log m)其中 n 和 m 分别是孩子和饼干的数量，主要时间消耗在排序上
空间复杂度O(1)只使用了常数级别的额外空间