贪心与堆简单1 种解法
#455分发饼干
每个孩子最多得到一块饼干，在尺寸满足胃口的前提下最大化被满足的孩子数。
#贪心#排序#双指针
原题
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 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 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1
注意：本题与 2410. 运动员和训练师的最大匹配数 题相同。
解题主线
- 排序后优先尝试满足胃口最大的孩子；若最大饼干都不够，该孩子不可能被任何剩余饼干满足。
- 当最大饼干能满足当前孩子时立即匹配，不会挤占更大胃口孩子的机会，因为更大的孩子已经处理完毕。
解法 1：排序加双指针
将胃口和饼干尺寸升序排序，从最大孩子与最大饼干开始；能满足就配对，否则跳过当前孩子。
-
时间复杂度： O(m log m + n log n)，m、n 分别为孩子数和饼干数
-
空间复杂度： O(log m + log n)，来自 Arrays.sort(int[]) 的调用栈
import java.util.Arrays;
final class Solution {
public int findContentChildren(int[] greed, int[] cookies) {
if (greed == null || cookies == null) {
throw new IllegalArgumentException("input arrays must not be null");
}
Arrays.sort(greed);
Arrays.sort(cookies);
int cookie = cookies.length - 1;
int contentChildren = 0;
// 从胃口和尺寸最大端匹配，确保大饼干优先服务更难满足的孩子
for (int child = greed.length - 1; child >= 0 && cookie >= 0; child--) {
// 最大剩余饼干不够时，仅跳过当前孩子，保留饼干给胃口更小者
if (cookies[cookie] >= greed[child]) {
contentChildren++;
// 只有匹配成功才消耗一块饼干
cookie--;
}
}
return contentChildren;
}
}实现提示
- 该实现延续旧源码的从大到小匹配策略，并显式记录成功匹配数。
边界与易错点
- 双指针方向要与贪心论证一致；从大到小时，孩子指针总移动，只有匹配成功才移动饼干指针。
- Arrays.sort(int[]) 会原地修改两个输入数组；若调用方需要保留顺序，应先复制数组。
- 空间复杂度若计入 Java 基本类型数组排序的递归栈，为 O(log m + log n)，并非严格 O(1)。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/greedy/Q455_findContentChildren.java