[LeetCode]Ar455. 分发饼干

🚩传送门：https://leetcode-cn.com/problems/assign-cookies/[

](https://leetcode-cn.com/problems/assign-cookies/solution/)

题目

你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

解题思路：排序 + 贪心 + 双指针

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。

证明如下：

假设有 m 个孩子，胃口值分别是 g(1)到 g(m) 假设有 n 个饼干，尺寸值分别是 s(1) 到 s(n)

满足下列式子 g(i)≤g(i+1)和 s(j)≤s(j+1)，其中 1≤i<m，1≤j<n。 (胃口越来越大，尺寸越来越大)

假设在对前 i−1 个孩子分配饼干之后，可以满足第 i 个孩子的胃口的最小的饼干是第 j 块饼干，即 s(j)是剩下的饼干中满足 g(i)≤s(j) 的最小值，最优解是将第 j 块饼干分配给第 i 个孩子。

如果不这样分配，考虑如下两种情形：

1. 如果 i<m 且 g(i+1)≤s(j) ，也成立，则如果将第 j 块饼干分配给第 i+1 个孩子，且还有剩余的饼干，则可以将第 j+1 块饼干分配给第 i 个孩子，分配的结果不会让更多的孩子被满足；
2. 如果 j<n，则如果将第 j+1 块饼干分配给第 i 个孩子，当 g(i+1)≤s(j) 时，可以将第 j 块饼干分配给第 i+1 个孩子，分配的结果不会让更多的孩子被满足；当 g(i+1)>s(j) 时，第 j 块饼干无法分配给任何孩子，因此剩下的可用的饼干少了一块，因此分配的结果不会让更多的孩子被满足，甚至可能因为少了一块可用的饼干而导致更少的孩子被满足。

基于上述分析，可以使用贪心的方法尽可能满足最多数量的孩子。

先对数组 g 和 s 排序，依次遍历 g 中的每个元素，对于每个元素找到能满足该元素的 s 中的最小的元素。

令 i 是 g 的下标，j 是 s 的下标，初始时 i 和 j 都为 0。

对于每个元素 g[i]，找到未被使用的最小的 j 使得 g[i]≤s[j]，则尺寸 s[j] 可以满足孩子胃口 g[i]。

由于 g 和 s 已经排好序，因此整个过程只需要对数组 g 和 s 各遍历一次。当两个数组之一遍历结束时，说明所有的孩子都被分配到了饼干，或者所有的饼干都已经被分配或被尝试分配（可能有些饼干无法分配给任何孩子），此时被分配到饼干的孩子数量即为可以满足的最多数量。

复杂度分析

时间复杂度：，其中 和 分别是数组 和 的长度。

对两个数组排序的时间复杂度是 ，遍历数组的时间复杂度是 ，因此总时间复杂度是 。

空间复杂度：，其中 和 分别是数组 和 的长度。

空间复杂度主要是排序的额外空间开销。

官方代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //1.排序
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length, numOfCookies = s.length;
        int count = 0,i=0,j=0;
        //2.遍历两个数组
        while(i<numOfChildren&&j<numOfCookies){
            //3. 如果该饼干不能满足孩子胃口,饼干指针右移
            if(g[i] > s[j]){
                j++;
            }else{
                //4.能满足,双指针同时移动
                i++;j++;count++;
            }
        }
        return count;
    }
}