本文共 1333 字，大约阅读时间需要 4 分钟。

一、题目描述

示例1：

示例2：

提示：

二、思路及题解

这是一道很好的贪心算法入门题目，如果了解贪心算法，这道题的解题思路就很容易想到。一起来看看~~~

2.1、思路

要求：家长尽可能的满足越多的孩子

• 每个孩子都有一个胃口值 g[i]（能让孩子满足胃口的饼干最小尺寸）
• 每块饼干都有一个尺寸 s[i]
• 当 s[index]>g[i] 时，可以将饼干index分给孩子 i 。
• 每个孩子最多只能分配一块饼干

因此，只要使得最小满足孩子 i 的饼干 index ，分配给孩子 i。那么就可使得最终可满足的孩子数最多，也就是说小尺寸饼干满足胃口小的孩子，大尺寸饼干满足胃口大的孩子。而这就是贪心算法的局部最优，从而使得全局最优。

先将饼干 s[i] 和孩子胃口 g[i] 进行升序排序，然后从右往左遍历孩子胃口 g[i] ,使得大饼干优先满足胃口大的孩子，最后统计满足小孩数量即可。如下图：

只要理解了大饼干优先满足胃口大的孩子（局部最优），从而使得最终饼干分配给孩子的人数达到最多（全局最优）。那么贪心算法再合适不过了~~~

2.2、题解

示例代码（Java）:

class Solution {
       public int findContentChildren(int[] g, int[] s) {
           //排序孩子胃口g[i]        Arrays.sort(g);        //排序饼干尺寸s[i]        Arrays.sort(s);        //标记饼干s[index]        int index = s.length-1;        int count = 0;        //从右向左遍历，使得大尺寸饼干优先满足胃口大的孩子        for(int i=g.length-1;i>=0;i--){
               if(index>=0&&s[index]>=g[i]){
                   index--;                count++;            }        }        return count;    }}

复杂度分析：

• 时间复杂度 O(mlogm+nlogn)：其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是O(mlogm+nlogn)，遍历数组的时间复杂度是 O(m)，因此总时间复杂度是O(mlogm+nlogn)。
• 空间复杂度 O(logm+logn)：其中 m 和 n 分别是数组 g 和 s 的长度。空间复杂度主要是排序的额外空间开销。

转载地址：https://blog.csdn.net/weixin_43452424/article/details/111699272 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！