算法D31 | 贪心算法1 | 455.分发饼干 376. 摆动序列 53. 最大子序和

贪心���法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。 

（）

不用花心思去研究其规律， 没有思路就立刻看题解。

基本贪心的题目 有两个极端，要不就是特简单，要不就是***活想不出来。  

（）

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

理论基础 

代码随想录

455.分发饼干  

代码随想录

两个数组先排序，倒着看最大的cookie能满足的孩子，向前计数。

Python:

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

C++:

C++版本用i--实现也算简洁。

class Solution {public:    int findContentChildren(vector& g, vector& s) {        sort(g.begin(), g.end());        sort(s.begin(), s.end());        int result=0;        int i = g.size()-1;        int j = s.size()-1;        for (int i=g.size()-1; i>=0; i--) {            if (j>=0 && s[j]>=g[i]) {                result++;                j--;            }        }        return result;    }};

376. 摆动序列  

代码随想录

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

主要难点：要考虑平坡的情况。

Python:

class Solution:    def wiggleMaxLength(self, nums: List[int]) -> int:        n = len(nums)        if n