贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
无固定套路，举不出反例，就可以试试贪心。
一般解题步骤：
1.将问题分解成若干子问题
2.找出适合的贪心策略
3.求解每一个子问题的最优解
4.将局部最优解堆叠成全局最优解
分发饼干
思路：为了满足更多的小孩，就不要造成饼干尺寸的浪费，大尺寸的饼干既可以满足胃口大的孩子，也可以满足胃口小的孩子，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略，先将饼干数组和小孩数组进行排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
class Solution{
public:
int findContentChildren(vector&g,vector& s){
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index = s.size() - 1;
int result = 0;
for(int i = g.size() - 1;i >= 0; i--){
if(index >= 0 && s[index] >= g[i]){
result++;
index--;
}
}
return result;
}
}; 从代码中可以看出，index用来控制饼干数组的遍历，遍历饼干没有再起一个循环，而是采用自减的方式，这是常用的技巧。
不可以先遍历比骨干再遍历胃口，因为外面for，i是固定移动的，if的index才是符合条件移动的。
反过来，先满足胃口小的，从小到大去满足：
class Solution{
public:
int findContentChildren(vector& g,vector&s){
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index = 0;
for(int i = 0; i < size(); i++){
if(index < g.size() && g[index] <= s[i]){
index++;
}
}
return index;
}
}; //思路一
class Solution{
public int findContentChildren(int[] g, int[] s){
Arrays.sort(g);
Arrays.sort(s);
int start = 0;
int count = 0;
for(int i = 0; i < s.length && start < g.length; i++){
if(s[i] >= g[start]){
start++;
count++;
}
}
return count;
}
} class Solution{
public int findContentChildren(int[] g,int[] s){
Arrays.sort(g);//排序胃口
Arrays.sort(s);//排序饼干
int count = 0;
int start = s.length - 1;//胃口数组长度，从start开始遍历，倒着遍历，先考虑胃口大的
//遍历胃口，从大到小
for(int index = g.length - 1;index >= 0;index--){
if(start >= 0 && g[index] <= s[start]){
start--;//从大到小
count++;//满足一个计数+1
}
}
return count;//返回计数
}
} 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在地话），可能是正数或负数，少于两个元素的序列也是摆动序列。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些元素来获得子序列，剩下的元素保持其原始顺序。
思路：
贪心
删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
实际操作中，删除操作都不用，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
这就是贪心所贪的地方， 让峰值尽可能地保持峰值，然后删除单一坡度上的节点。
在计算是否有峰值的时候，大家知道遍历的下标i，计算presiff(nums[i] - nums[i - 1])和curdiff(nums[i + 1] - nums[i]),如果presiff < 0 && surdiff > 0或者prediff > 0 && curdiff < 0，此时就有波动就需要统计。
这是我们思考本题的一个大体思路，但本题还要考虑三种情况：
1.上下坡有平坡
[1，2，2，2，2，1]删除左边的三个2，或者删除右边的三个2，摆动长度为3
当i指向第一个2的时候，prediff > 0&&curdiff=0，当 i 指向最后一个2的时候，prediff=0 && curdiff <0.
如果采用删除左面三个2的规则，那么当prediff = 0&&curdiff < 0也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。
我们记录峰值的条件应该是：(preDiff <=0 &&curDiff > 0)||(preDiff >= 0&&curDiff < 0)
2.数组首尾两端
本题统计峰值的时候，数组最左面和最右面如何统计。
当有两个不同的元素时，摆动序列也是2.
例如[2,5],如果靠统计差值来计算峰值个数，就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算prediff（nums[i] - nums[i - 1]）和curdiff(nums[i+1] - nums[i])的时候，至少需要三个数字才能计算，而数组只有两个数字。这里如果只有两个数字，且是不同的元素，那结果为2.
3.单调坡中有平坡
之前我们在讨论 情况一 ：相同数字练习的时候，prediff = 0，curdiff < 0或者>0也记为波谷
为了统一规则。针对序列[2,5],可以假设为[2,2,5],这样就有了坡度，即preDiff = 0.
[2,2,5]
针对以上情形，result初始值为1，此时curDiff > 0&&preDiff<=0,那么result++(计算了左面的峰值)，最后得到结果为2（峰值个数为2即摆动序列长度为2）
class Solution{
public:
int wiggleMaxLength(vector&nums){
if(num.size() <= 1)return nums.size();
int curDiff = 0;
int preDiff = 0;
int result = 1;
for(int i = 0; i < nums.size() - 1;i++){
curDiff = nums[i + 1]-nums[i];
if((preDiff <= 0 &&curDiff >0)||(preDiff >= 0 && curDiff < 0)){
result++;
}
preDiff = curDiff;
}
};
} 3.在上面解法中，忽略了第三种情况，即如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]
图中我们可以看出，应该记录2，单调中的平坡不能算作峰值（摆动）
需要在坡度摆动变化时，更新prediff，这样prediff在单调区间有平坡的时候就不会发生变化，造成误判。
class Solution{
public:
int wiggleMaxLength(vctor&nums){
if(nums.size() <= 1)return nums.size();
int curDiff = 0;
int preDiff = 0;
int result = 1;
for(int i = 0; i < nums.size() - 1;i++){
curDiff = nums[i + 1] - nums[i];
//出现峰值
if((preDiff <= 0 && curDiff > 0)||(preDiff >= 0&& curDiff < 0)){
result++;
preDiff = curDiff;
}
}
return result;
}
}; 用动态规划求解
思路：
对于我们当前考虑的这个数，要么是作为山峰（nums[i] > nums[i - 1]）,要么是作为山谷（即nums[i] < nums[i-1]）
设dp状态dp[i][0],表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度。
设dp状态为dp[i][1],表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
//设dp状态dp[i][0],表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
//设dp状态dp[i][1],表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
class Solution{
public:
int wiggleMaxLength(vector&nums){
memset(dp,0,sizeof dp);
dp[0][0] = dp[0][1] = 1;
for(int i = 1;i < nums.size(); ++i){
dp[i][0] = dp[i][1] = 1;
for(int j = 0;j < i;++j){
if(nums[j] > nums[i])dp[i][1] = max(dp[i][1],dp[j][0]+1);
}
for(int j = 0;j < i; ++j){
if(nums[j] < nums[i])dp[i][0] = max(dp[i][0],dp[j][1] + 1);
}
}
return max(dp[nums.size() - 1][0],dp[nums.size() - 1][1]);
}
}; 最大子序和
//记录局部最优，推出全局最优，相当于暴力求解+调整子区间起始位置，用了一个result来更新和记录最大结果count
class Solution{
public:
int maxSubArray(vector&nums){
int count = 0;
for(int i = 0;i < nums.size(); i++){
count += nums[i];
if(count > result){
result = count;//更新最大值
}
if(count <= 0)count = 0;//重置最大子序列的初始位置
}
return result;
}
};