贪心算法专题(一)：局部最优的魔力——“抠门”的「分发饼干」-深圳市維司達科技有限公司

哈喽各位，我是前端小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) 取决于排序算法的实现)
- 我们只需要几个变量，不需要额外的数组空间。