LeetCode题目链接
这道题目就是你有一个饼干数组，里面表示你有几块不同大小的饼干，然后呢有一个小孩数组，表示有几个不同胃口大小的小孩，你要分配饼干尽可能让最多的孩子得到满足，然后输出得到满足的孩子数量????????????
我们来思路梳理
- 首先将孩子的胃口值数组
g和饼干的尺寸数组s进行升序排序。从胃口最小的孩子开始，用最小尺寸的饼干去满足。这样可以最大化地利用较小的饼干，避免浪费大饼干????????????（小饼干满足小胃口） - 先将孩子的胃口和饼干尺寸排序。从胃口最大的孩子开始，用尽可能大的饼干去满足。这样可以保证较大的饼干不浪费在小胃口的孩子上????????????（大饼干满足大胃口）
这里我们就以第一种策略为例来分析贪心的四个子逻辑
-
如何判断最优解
- 最优解的目标是尽可能多地满足孩子的胃口????????????为了达到这个目标，选择一种贪心策略来匹配饼干和孩子的胃口。通过排序和逐一分配饼干，可以确保每次都能做出最优选择——满足当前最小的胃口
-
判断局部最优选择的可行性
- 局部最优选择是尽量用最小的饼干去满足胃口最小的孩子????????????这样我们不会浪费大尺寸的饼干，可以为更大胃口的孩子保留大尺寸的饼干
-
更新问题状态
- 每当分配一个饼干给孩子时，我们需要移除已分配的饼干，表示该饼干已经用过????????????移除已满足的孩子，表示该孩子已经满足胃口????????????接着处理下一个未满足的孩子和未使用的饼干
-
重复选择
- 不断重复上述过程，直到饼干或孩子处理完毕。每次都选择最小的饼干去匹配最小的胃口，保证每次都是局部最优解????????????
贪心算法完整代码如下
class Solution {
public int findContentChildren(int[] g, int[] s) {
//将胃口数组和饼干尺寸数组进行升序排序
Arrays.sort(g);
Arrays.sort(s);
//初始化遍历孩子数组和饼干数组的索引
int childIndex = 0;
int cookieIndex = 0;
//重复选择：当还有未处理的孩子和饼干时进行分配
while(childIndex < g.length && cookieIndex < s.length){
//判断局部最优选择的可行性
if(s[cookieIndex] >= g[childIndex])childIndex++;//更新问题状态
cookieIndex++;//更新问题状态
}
return childIndex;//最优解即是被满足孩子的数量
}
}