31天【代码随想录算法训练营34期】第八章 贪心算法 part01(● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和 )

贪心算法就是先选局部最优，再推全局最优
没有套路

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

● 455.分发饼干

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        output = 0
        s_i = len(s)-1

        for i in range(len(g)-1, -1, -1):
            if s_i >= 0 and g[i] <= s[s_i]:
                output += 1
                s_i -= 1
        return output
        

● 376. 摆动序列
● 53. 最大子序和