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

这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

455.分发饼干

大胃口先吃大饼干（for胃口，if饼干，不能反过来否则胃口太大，一个饼干都满足不了直接跳过了）和小饼干给小胃口吃（for饼干，if胃口,不能反过来，否饼干太小满足不了最小的胃口也会跳过）都可以

//C++ 先分配小饼干
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int cnt = 0;
        int index = 0;
        for (int i = 0 ; i < s.size(); i++) {
            if (index < g.size() && s[i] >= g[index]) {
                cnt++;
                index++;
            }
        }
        return cnt;
    }
};
//C# 先满足大胃口
public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        int cnt = 0;
        Array.Sort(g);
        Array.Sort(s);
        int index = s.Length - 1;
        for (int i = g.Length - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                cnt++;
                index--;
            }
        }
        return cnt;
    }
}

376. 摆动序列

让峰值尽可能的保持峰值，然后删除单一坡度上的节点，转化为求峰值点的个数.

情况一：上下坡中有平坡

记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0),相当于只保留左平右下和左平右上的情况，删除左边三个2。

情况二：数组首尾两端

默认序列最右边带一个峰，这样两个数的时候也符合情况1会加1得到2

情况三： 单调坡度有平坡

让preDiff在发生摆动的时候再更新，避免单调平坡错误统计。

//C++
class Solution {
public:
    int wiggleMaxLength(vector<int>& 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 (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
};
// C#
public class Solution {
    public int WiggleMaxLength(int[] nums) {
        if (nums.Length == 0) return 0;
        int curDiff = 0;
        int preDiff = 0;
        int result = 1;
        for (int i = 0; i < nums.Length - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
}

53. 最大子序和

局部最优：计算连续和，为负数重新计算sum。

全局最优：过程中用result记录最优的局部连续和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
          	//先记录，避免最大自序和为负数被覆盖为0
            if (sum > result) {
                result = sum;
            }
            sum += nums[i];
            if (sum < 0) {
                sum = 0;
            }
        }
        return result;
    }
};