代码随想录第28天|贪心算法part2

122买卖股票的最佳时机2

在这里插入图片描述
贪心算法最好能写出表达式，这样才好推导
假设在i天买入，j天卖出，则利润:price[j]-price[i] = (price[j]-price[j-1])+(price[j-1]+price[j-2])+...+(price[i+1]-price[i])
于是我们可以计算出相邻天数的价格差，如果为正，就加入结果，否则跳过在这里插入图片描述
如该图，4，5，3是正的，这代表：在4的前一天，价格为1买入，在5的那天，价格为10卖出，在3的前一天，价格为3的时候买入，价格为6的时候卖出，总利润为12

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

55.跳跃游戏

在这里插入图片描述
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
遍历每个位置，更新能到达的最大边界，如果当前遍历到的位置是之前所能跳跃到的最大位置且该位置所能跳跃的长度为0，且当前位置不为右边界的话，说明只能呆在该位置到不了右边界，返回false即可

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

45.跳跃游戏II

在这里插入图片描述
局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。因为到达了当前这一步的最大覆盖范围的时候，下一步的最大范围又更新过了，所以说必定走过更新覆盖范围的那一步
比如[2,3,1,1,4]，第一步就更新了最大覆盖范围到下标为2，当前覆盖范围为2，第二步的时候更新了最大覆盖范围到下标4，而这个时候并没有走到下标2，所以当走到下标2的时候，就需要走一步且更新当前覆盖范围为4，因为是边界，所以退出循环。这意味着走到了第一步的覆盖范围的时候，因为没到最后右边界，所以需要跳到之前能够更新最大覆盖范围的那一步(都更新过了最大覆盖范围，说明肯定比当前覆盖范围小，比如3就在1的前面），就如从第一步跳到第二步，然后更新当前覆盖范围，这个时候说明能从第二步跳到最后了，所以结束循环。（第一步一定要起跳，所以更新覆盖范围的时候res要+1）
2->3->末尾4
在这里插入图片描述