day 31 贪心（1）

day31
代码随想录
2023.12.29

今天开始贪心之路！
贪心的本质很简单，就是选取每一阶段的局部最优，从而达到全局最优。听起来很简单，但是遇到题就不一样了，有的非常简单，简单到你没有意识到自己用了贪心，但有的很难，难到无从下手。

贪心算法一般分为如下四步：

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

当然，这是一个粗略的大致步骤，真正做题要灵活运用。

1. 455分发饼干
这道题就是比较典型的贪心的，局部最优的点在于，针对孩子需求，每次饼干找刚好满足的，也就是说对于g数组中的数，遍历中找s中满足且最小的值！每次遍历达到这种效果，整体遍历就是满足孩子数量最多的了，至于代码写法也有很多了，开始写的时候，还有点写不出来，就多写了一个bool函数，表示饼干是否已经分发给孩子了，

class Solution {
public:
    bool find(int num, vector<int>& s, vector<bool>& used){
        for(int i=0;i<s.size();i++){
            if((num<s[i] || num==s[i]) && used[i]==false){//找到满足条件的饼干，值满足且最小且未分发给孩子
                used[i] = true;
                return true;
            }
        }
        return false;
    }
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int result = 0;
        vector<bool> used(s.size(), false);
        if(s.size()==0){
            return result;
        }
        sort(s.begin(), s.end());
        sort(g.begin(), g.end());
        for(int i=0;i<g.size();i++){
            if(find(g[i],s, used)){
                result++;
            }
        }
        return result;
    }
};

2. 376摆动序列
这道题，看蒙了，不会做，还要删除节点，剩余节点满足最大摇摆序列，数组删除都麻烦，难不成每次删除然后位置都动一动？看文字讲解后发现，只需要统计满足要求的峰值就行（最大或最小），而峰值判断就是一个点两边差值正负相反。问题实际情况可能有很多种，平坡，一直是上坡、下坡等等，这种情况怎么办，以为又要分别判断了，但最后发现，就算有这些情况，不用做处理啊，直接跳过就行了，我们要的只有坡峰，所以只需要在坡峰时做一些操作就行，首先肯定结果数++，最后就是这个前后差值，后差值并不是值得当前节点紧挨的后插值，而是上次满足坡峰要求是的前差值，到这个点就变成后差值了，因此这个后差值，只需要在满足坡峰要求时更新就好，仔细想想，这个操作也就是将刚才说的各种情况全部跳过去的意思

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 ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff
            }
        }
        return result;
    }
};

3. 53最大子数组和
这道题跟上道题，都感觉贪心有点牵强，这道题就是在遍历时候，当和小于0，也就是负数的时候重新计数，因为，一旦和是负数了，则就是拉低整体和的，所以就不能算最大值，因此当和为负数时，更新和为0，也就是变量调整了起始位置。

int result = INT32_MIN;
        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;