：局部最优的魔力——“抠门”的「分发饼干」)
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第一篇！ 贪心算法没有固定的套路模板（不像回溯有backtrack模板，DP 有dp数组）。贪心的核心在于策略。
我们通过“分发饼干”这道题来感受一下：假设你是一位精打细算的家长，手里有一堆大小不一的饼干，面前站着一堆胃口大小不一的孩子。你的目标是喂饱尽可能多的孩子，但为了不浪费，你应该怎么分？
力扣 455. 分发饼干
https://leetcode.cn/problems/assign-cookies/
题目分析：
输入：
g(greed factor)：数组，表示每个孩子的胃口值（最小能吃饱的量）。s(size)：数组，表示每块饼干的大小。
规则：如果
s[j] >= g[i]，我们可以把饼干j给孩子i，这个孩子就满足了。目标：尽可能满足更多的孩子。
核心思维：大饼干喂大胃口，还是小饼干喂小胃口？
如果我们随便分：
拿一块超级大的饼干，喂给一个胃口很小的孩子 ->浪费（大饼干本可以喂给大胃口的孩子）。
拿一块很小的饼干，喂给一个胃口很大的孩子 ->无效（孩子吃不饱，饼干也没了）。
贪心策略一（小喂小）：优先用最小的饼干，去喂胃口最小的孩子。
如果这块最小的饼干能满足他，那就给他（局部最优：既喂饱了一个，又保留了较大的饼干给后面）。
如果这块饼干连最小胃口都满足不了，那这块饼干就是废的，谁也喂不饱，丢掉（也就是换下一块大一点的）。
贪心策略二（大喂大）：优先用最大的饼干，去喂胃口最大的孩子。
如果最大的饼干能满足最大的胃口，那就给他。
如果满足不了，说明这个大胃口的孩子谁也救不了，放弃他，看下一个胃口稍微小一点的孩子。
这两种策略都是对的！为了便于实现，我们通常选择**“先排序，再匹配”**。
算法流程 (策略一：小饼干先喂小胃口)
排序：将孩子的胃口
g和饼干大小s都从小到大排序。双指针遍历：
child指向第 0 个孩子。cookie指向第 0 块饼干。
循环判断：
如果
s[cookie] >= g[child]：太好了，这块饼干正好（或勉强）能喂饱这个孩子。
child++(换下一个孩子)。cookie++(换下一块饼干)。
如果
s[cookie] < g[child]：这块饼干太小了，连胃口最小的孩子都满足不了。
cookie++(换一块更大的试试，孩子原地不动)。
结束：
child的数值就是被满足的孩子总数。
代码实现 (C++)
C++
#include <vector> #include <algorithm> using namespace std; class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { // 1. 贪心的前提通常是“有序” sort(g.begin(), g.end()); sort(s.begin(), s.end()); int child = 0; int cookie = 0; // 2. 遍历饼干和孩子 while (child < g.size() && cookie < s.size()) { // 如果当前的饼干能满足当前的孩子 if (s[cookie] >= g[child]) { child++; // 孩子吃饱了，换下一个 } // 无论能不能满足，这块饼干都“消耗”了 // (如果满足了，被吃了；如果不满足，它太小了没用，被跳过) cookie++; } return child; } };深度复杂度分析
时间复杂度：O(N log N + M log M)
瓶颈在于排序。
g和s的排序分别需要N log N和M log M。后面的双指针遍历只需要
O(N + M)。
空间复杂度：O(1)(或 O(log N) 取决于排序算法的实现)
我们只需要几个变量，不需要额外的数组空间。
总结：贪心的第一准则
今天这道题虽然简单，但它揭示了贪心算法最重要的两个特征：
排序：大多数贪心问题，都需要在有序的数据上才能进行“最优选择”。如果题目没给有序数组，你往往需要先
sort。局部最优 -> 全局最优：
局部最优：这块饼干哪怕只比孩子的胃口大一点点，我也给它用了，绝不浪费更大的饼干。
全局最优：最后喂饱的孩子最多。
这种**“没有后效性”**（现在的选择不会影响未来的可行性，只会让未来更好做）是贪心算法生效的基础。
下一题预告： 如果情况稍微复杂一点，我们面对的不是静态的饼干，而是一个波动的序列。我们要在一个忽高忽低的序列中，统计“峰值”和“谷值”的变化次数（摆动序列）。这道题将展示如何通过**忽略“平坡”**这一局部贪心策略来解决问题。
下期见！
