代码随想录算法训练营第三十二天|122.买股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II

文档讲解：
贪心算法

122.买股票的最佳时机II

思路：先bb一句，其实这道题有点扯淡，咋能这么买股票hhh。具体思路还是十分容易的，就是要拆解利润，因为我们已知这几天的利润，那么我们有个最简单暴力的做法，就是我们今天买了，明天卖了就能赚钱，以两天为一个小区间，来拆解大区间！在数学上的表达式：prices[i+1]-prices[i]，只要维持整个区间的每个小区间是赚钱的，加起来那么肯定就是最大盈利！(和昨天的摆动序列思路有点像，但是这道题需要你自己去分解，难点不同，但是只要分解出来了，代码难度小于摆动序列的)
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
   
public:
    int maxProfit(vector<int>& prices) {
   
        int maxfit=0;
        int prediff=0;
        for(int i=0;i<prices.size()-1;i++)
        {
   
            prediff=prices[i+1]-prices[i];
            if(prediff<=0) continue;
            maxfit+=prediff;
        }
        return maxfit;
    }
};

55.跳跃游戏

思路：一开始还是没想到范围的问题，关注点其中是否有0，故这道题关键点在于最大覆盖范围是否大于nums.size()，请注意for循环的条件是<=cover，我们只能在我们能覆盖到的范围内循环！
时间复杂度：O(n)
空间复杂度：O(1)

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

45.跳跃游戏II

思路：关键点还是在于最大覆盖范围，在于什么时候去更新覆盖范围，那么就是将目前的范围遍历一遍，得到最大的下一个覆盖范围，进行更新，更新后立即判断是否覆盖了整个数组，如果覆盖，即能跳出，若不覆盖，将上述过程重复一遍！
时间复杂度：O(n)
空间复杂度：O(1)

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