贪心

方法一贪心

要想要满足的孩子最多就要先从需求小的孩子满足，如果需求小的都满足不了就更满足不了需求大的了。同时供应饼干也需要从量小的进行考虑，避免出现田忌赛马的问题。
把需求量和饼干从小到大排序，如果当前饼干可以满足孩子，那么就把饼干分配给孩子，否则就换一个更大的饼干。直到满足了所有孩子活着饼干遍历结束。

参考代码

  1. class Solution:
  2.     def findContentChildren(self, g: List[int], s: List[int]) -> int:
  3.         g.sort()
  4.         s.sort()
  5.         i,j = 0,0
  6.         ans = 0
  7.         while i < len(g) and j < len(s):
  8.             if g[i] <= s[j]:
  9.                 ans += 1
  10.                 i += 1
  11.                 j += 1
  12.             else:
  13.                 j += 1
  15.         return ans

复杂度分析

时间复杂度 455. 分发饼干 - 图1m和n是数组g和s的长度。主要是排序使用的时间复杂度
空间复杂度 455. 分发饼干 - 图2 主要是排序使用的空间复杂度