贪心算法补卡

376. 摆动序列

首先是对“摆动”的判断，为什么等于号要在同一边，可以在一个平坡中只计算一次左边的平坡到上坡或者下坡，为了避免两端的特殊判断，右端结束算一个坡，所以答案初始是1，在开头加上和第一个元素大小一致的头元素，漏掉了单调中包含平坡误判的情况，因为以下判断方法是每次更新predis，然后判断当前dis，如果是一次摆动就算入，因为考虑到了平坡，虽然只会梯形的平坡算入一次拐点，但是存在单调区间的拐点，也会被算进去，所以如果是在一个单调区间里面，不应该把pre改成0，造成在单调区间里峰值的误判，而是在有峰值的时候，单调的方向真的改变了，才把predis更改正负

(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)

55. 跳跃游戏

 因为可以选择步数范围内跳几步，范围就是i+nums[i]，然后进一步更新最大范围

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxx = 0;
        for(int i = 0;i<=maxx;i++){
            if(maxx>=nums.size()-1) return true;
            maxx = max(maxx, i+nums[i]);
        }
        return false;
    }
};

45.跳跃游戏II

这里我自己做的思路和解析有些区别，这里我把return ans 放在i>premax之前，而判断return的时候返回的ans，是通过当前的maxx（也就是下一次跳跃的范围，也就是ans+1的范围）就会导致我刚开始需要ans=1, 这里我代码繁琐的主要问题是没有弄清楚ans对应的当前步数范围，还是下一步数范围

 

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<=1) return 0;
        int maxx = 0;
        int ans = 1;
        int premax = maxx;
        for(int i = 0;i<=maxx;i++){
            if(maxx>=nums.size()-1) return ans;
            if(i>premax){
                premax = maxx;
                ans++;
            }
            maxx = max(maxx, i+nums[i]);
        }
        return ans;
    }
};