What is the main pattern used in Assign Cookies?

The problem uses a two-pointer scanning pattern combined with greedy sorting to assign the smallest sufficient cookie to each child.

Why do we sort both arrays before assigning cookies?

Sorting ensures that the smallest available cookie is matched with the least greedy child first, maintaining the greedy invariant.

How do two pointers work in this problem?

One pointer tracks children and the other tracks cookies; pointers increment based on whether the current cookie satisfies the current child.

Can a child receive more than one cookie?

No, each child can receive at most one cookie, which is central to maintaining the two-pointer invariant.

What are common mistakes when implementing Assign Cookies?

Common mistakes include not sorting arrays, mismanaging pointer increments, and failing to count content children accurately.

#455

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 g[i] ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s[j] 。如果 s[j] >= g[i] ，我们可以将这个饼干 j 分配给孩子 i ，这…

数组双指针贪心排序

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]_，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

提示：

1 <= g.length <= 3 * 10⁴
0 <= s.length <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 1

注意：本题与 2410. 运动员和训练师的最大匹配数题相同。

lightbulb

解题思路

方法一：排序 + 双指针

根据题目描述，我们应该优先将饼干分配给胃口值小的孩子，这样可以尽可能满足更多的孩子。

因此，我们首先对两个数组进行排序，然后用两个指针 $i$ 和 $j$ 分别指向数组 $g$ 和 $s$ 的头部，每次比较 $g[i]$ 和 $s[j]$ 的大小：

如果 $s[j] \lt g[i]$ ，说明当前饼干 $s[j]$ 无法满足当前孩子 $g[i]$ ，我们应该将尺寸更大的饼干分配给当前孩子，因此 $j$ 应该右移一位；如果 $j$ 越界，说明无法满足当前孩子，此时成功分配的孩子数量为 $i$ ，直接返回即可；
如果 $s[j] \ge g[i]$ ，说明当前饼干 $s[j]$ 可以满足当前孩子 $g[i]$ ，我们将当前饼干分配给当前孩子，因此 $i$ 和 $j$ 都应该右移一位。

如果遍历完数组 $g$ ，则说明所有孩子都已经分配到饼干，则返回孩子总数即可。

时间复杂度 $O(m \times \log m + n \times \log n)$ ，空间复杂度 $O(\log m + \log n)$ 。其中 $m$ 和 $n$ 分别为数组 $g$ 和 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        j = 0
        for i, x in enumerate(g):
            while j < len(s) and s[j] < g[i]:
                j += 1
            if j >= len(s):
                return i
            j += 1
        return len(g)

speed

复杂度分析

指标	值
时间	complexity is O(n log n + m log m) due to sorting both arrays, where n is the number of children and m is the number of cookies. Two-pointer scanning is O(n + m), and space complexity is O(n + m) for storing sorted arrays.
空间	O(m + n)

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate sort arrays before scanning?
question_mark
Are two pointers used efficiently to assign cookies?
question_mark
Is the invariant maintained so no child is skipped incorrectly?

warning

常见陷阱

外企场景

error
Failing to sort arrays before scanning, leading to suboptimal assignments.
error
Not maintaining two-pointer invariant, resulting in skipped children or incorrect counts.
error
Incorrectly incrementing pointers, causing double assignment or missed content children.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reverse the problem: minimize cookies used to satisfy all children.
arrow_right_alt
Allow multiple cookies per child, requiring modification of two-pointer logic.
arrow_right_alt
Children or cookies are extremely large, testing time and space efficiency under constraints.

help

常见问题

外企场景

继续练习

#581 最短无序连续子数组 #611 有效三角形的个数 #826 安排工作以达到最大收益