题目描述
思路解析动画文字版
这题的关键是先排序,让“当前最容易满足的孩子”和“当前最小的饼干”可以直接比较。
不够当前最小胃口孩子的饼干,也不可能满足后面胃口更大的孩子。
排序后开始:g=[1,2,3],s=[1,1,2,3]:主行展示排序后的饼干 s;变量面板固定展示孩子胃口 g 和当前孩子 g[i]。i 表示已经满足了多少个孩子,也表示下一个孩子下标。
进入 for:从最小饼干开始试:高亮的是当前扫描到的饼干 s[0]。每一轮只问:当前这块最小可用饼干,能不能满足当前最小胃口孩子。
第 1 块饼干 1:满足 g[0]=1:s[0] 被标为已匹配:最小饼干 1 正好满足最小胃口 1。用掉它后,i=1,下一位孩子的胃口是 2。
第 2 块饼干 1:不够 g[1]=2:s[1] 被置灰表示跳过。它连当前最小胃口孩子都不够,更不可能满足后面的孩子,所以 i 不移动。
第 3 块饼干 2:满足 g[1]=2:尺寸 2 的饼干刚好满足胃口 2 的孩子。继续把更大的饼干留给后面的孩子。
第 4 块饼干 3:满足 g[2]=3:最后一块饼干满足胃口 3 的孩子。此时 i=3,三个孩子都已满足。
所有孩子已满足:i == len(g):如果后面还有饼干,条件 i < len(g) 会阻止继续访问 g[i]。这里已经没有孩子需要满足。
返回满足数量:i 的含义一举两得:既是下一个孩子下标,也是当前已经满足的孩子数量。
排序以后,每次局部选择都不会伤害未来,因为后面的孩子胃口只会更大。
参考代码
class Solution: def findContentChildren(self, g, s): g.sort() s.sort() i = 0 for cookie in s: if i < len(g) and cookie >= g[i]: i += 1 return i复杂度
- 时间复杂度:O(n log n + m log m),n 是孩子数量,m 是饼干数量,主要开销来自两次排序。
- 空间复杂度:O(1),除排序实现内部开销外,只使用 i 等常数变量。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
种花问题
LeetCode 605 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题