贪心与堆简单1 种解法

#455分发饼干

每个孩子最多得到一块饼干，在尺寸满足胃口的前提下最大化被满足的孩子数。

#贪心#排序#双指针

解题主线

排序后优先尝试满足胃口最大的孩子；若最大饼干都不够，该孩子不可能被任何剩余饼干满足。

当最大饼干能满足当前孩子时立即匹配，不会挤占更大胃口孩子的机会，因为更大的孩子已经处理完毕。

解法 1：排序加双指针

将胃口和饼干尺寸升序排序，从最大孩子与最大饼干开始；能满足就配对，否则跳过当前孩子。

时间复杂度

O(m log m + n log n)，m、n 分别为孩子数和饼干数

空间复杂度

O(log m + log n)，来自 Arrays.sort(int[]) 的调用栈

455. 分发饼干 · 排序加双指针

java

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