455. 分发饼干

🟢   🔖  贪心 数组 双指针 排序  🔗 力扣 LeetCode

题目

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.

And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.

You need to output 1.

Example 2:

Input: g = [1,2], s = [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.

You have 3 cookies and their sizes are big enough to gratify all of the children,

You need to output 2.

Constraints:

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

Note: This question is the same as 2410. Maximum Matching of Players With Trainers.

题目大意

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

对每个孩子 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^4
• 0 <= s.length <= 3 * 10^4
• 1 <= g[i], s[j] <= 231 - 1

注意： 本题与 2410. 运动员和训练师的最大匹配数 题相同。

解题思路

为了最大化满足孩子们的需求，可以采用贪心算法来解决这个问题。

1. 排序：首先，对孩子们的胃口值数组 g 和饼干的尺寸数组 s 进行排序。排序后，可以依次尝试给每个孩子分配最小的满足条件的饼干。
2. 使用两个指针 i 和 j 分别遍历孩子和饼干数组，对于每个孩子，尝试找到一个符合条件（即饼干尺寸大于等于孩子胃口值）的饼干：
   • 如果 s[j] >= g[i]，就给孩子 i 分配饼干 j，然后 i++ 和 j++。
   • 如果 s[j] < g[i]，则当前饼干无法满足孩子，j++，尝试下一个饼干。
   • 当没有更多的孩子或饼干时，就停止。
3. 最后返回分配的饼干数量 count。

复杂度分析

• 时间复杂度：O(n log n)。
  • 排序需要 O(n log n) 时间，其中 n 是孩子或饼干数组的长度。
  • 遍历数组需要 O(n) 时间。
  • 总时间复杂度为 O(n log n)，因为排序是最耗时的操作。
• 空间复杂度：O(1)，只使用了常数空间来存储一些指针和计数器。

代码

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
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;
};