455. 分发饼干
题目描述
数组 g 给出每个孩子的胃口：g[i] 是让第 i 个孩子满意所需的最小饼干尺寸。数组 s 给出每块饼干的尺寸。
当 s[j] >= g[i] 时，把饼干 j 给孩子 i 就能让他满意。每个孩子最多拿一块，每块饼干也只能给一个孩子。
返回最多能让多少个孩子满意。
示例 1
输入：g = [1,2,3], s = [1,1] 输出：1
解释：两块饼干尺寸都是 1，只能满足胃口为 1 的那个孩子。
示例 2
输入：g = [1,2], s = [1,2,3] 输出：2
解释：饼干足够大也足够多，两个孩子都能满足。
数据范围
1 <= g.length <= 3 * 10^40 <= s.length <= 3 * 10^41 <= g[i], s[j] <= 2^31 - 1
解题思路
把胃口和饼干都从小到大排序。从小到大遍历饼干，指针 i 指向胃口最小的还没满足的孩子：当前饼干能满足他就分给他（i 加 1），否则这块饼干连最小的胃口都满足不了，直接丢弃。小饼干优先给小胃口，大饼干留给后面更大的胃口。
为什么正确
前 i 个胃口最小的孩子已被满足；已经遍历过的饼干要么分出去了，要么比 g[i] 还小、对后面的孩子也无用。
复杂度分析
时间 O(n log n + m log m)，空间 O(log n + log m)（排序栈）。
易错点
要先判断 i < len(g)：孩子都满足后仍可能有剩下的饼干，不能越界访问 g[i]。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
i = 0
for size in s:
if i < len(g) and size >= g[i]:
i += 1
return iclass Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
for (int size : s) {
if (i < g.length && size >= g[i])
i++;
}
return i;
}
}class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0;
for (int size : s) {
if (i < (int)g.size() && size >= g[i])
i++;
}
return i;
}
};func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
i := 0
for _, size := range s {
if i < len(g) && size >= g[i] {
i++
}
}
return i
}var findContentChildren = function(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let i = 0;
for (const size of s) {
if (i < g.length && size >= g[i])
i++;
}
return i;
};function findContentChildren(g: number[], s: number[]): number {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let i = 0;
for (const size of s) {
if (i < g.length && size >= g[i])
i++;
}
return i;
}