代码随想录Day32 | 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

122.买卖股票的最佳时机II
55.跳跃游戏
45.跳跃游戏II

122.买卖股票的最佳时机II

文档讲解：代码随想录
视频讲解：贪心算法也能解决股票问题！LeetCode：122.买卖股票最佳时机 II
状态

考虑买和卖的时机，在峰谷买，在峰顶卖。当我们的数组一直降序那就不买，直到出现上升买入，然后如果一直上升就不卖，直到出现下降卖出

//当下降不买
//当下一个大，开始买入
//当买入后，开始下降卖出
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //返回的利润
        int res = 0;
        //买入股票
        int buy = -1;
        //注意边界
        for(int i=0;i<prices.size()-1;i++)
        {
            if(prices[i] > prices[i+1] && buy == -1)
            {
                continue;
            }
            if(prices[i] > prices[i+1] && buy != -1)
            {
                
                res += prices[i]-buy;
                buy = -1;
            }
            if(prices[i] < prices[i+1] && buy == -1)
            {
                buy = prices[i];
            }
            //考虑最后一个数的影响
            if(i == prices.size()-2 && prices[i+1] >= prices[i] && buy != -1)
            {
                cout << buy << " ";
                res += prices[i+1] - buy;
                buy = -1;
            }
        }
        return res;
    }
};

贪心 – 谨慎购买
类似于前缀和，当前位置的利润等于前面利润的总和+新增的利润，那么当前最大的利润就是前面的连续正数利润之和。我们可以这样想，当遇到第二天比第一天大的就卖掉，然后如果第三天比第二天还大那么就买回第二天然后第三天卖掉。这样一来相当于我们会收取所有利润为正数的。结果一定是最大值


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //返回的利润
        int res = 0;
        for(int i = 1;i<prices.size();i++)
        {
            res += max(prices[i]-prices[i-1],0);
        }
        return res;
    }
};

55.跳跃游戏

文档讲解：代码随想录
视频讲解：贪心算法，怎么跳跃不重要，关键在覆盖范围 | LeetCode：55.跳跃游戏
状态

每次考虑的是当前节点能否直接跳到终点，如果能够跳到就为true，要注意节点的边界，应当为当前节点跳跃范围内，如果当前节点的跳跃范围变大，那么可以更新。即寻找这个跳跃范围中能够跳跃的最远节点为边界

//每个点能够跳跃的最大位置是否能够到达终点
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int canJump = 0;
        for(int i = 0;i<=canJump;i++)
        {
            canJump = max(i+nums[i],canJump);
            if(canJump >= nums.size()-1)
            {
                return true;
            }
        }
        return false;
    }
};

45.跳跃游戏II

文档讲解：代码随想录
视频讲解：贪心算法，最少跳几步还得看覆盖范围 | LeetCode： 45.跳跃游戏 II
状态

最小跳跃次数，就是在当前范围中，选择那一个使得修改边界最大的下标跳过去，那么就是遍历完这个当前范围，那么跳跃1次，同时更新当前范围为记录的最大边界，进行下一次的跳跃等待。如果下一的跳跃即用来更新边界的数超过了末尾，那么直接退出即可。

//题目保证可以跳到
//最小次数，就是在之前范围中能够更新边界的最大位置，直接从当前节点跳到那个位置
class Solution {
public:
    int jump(vector<int>& nums) {
        int canJump = 0;
        int jumptimes = 0;
        //记录当前遍历的边界
        int board = 0;
        if(nums.size()==1) return jumptimes;
        for(int i=0;i<=nums.size()-1;i++)
        {
            canJump = max(nums[i]+i,canJump);
            if(i == board)
            {
                board = canJump;
                jumptimes++;
                if(canJump >= nums.size()-1) break;
            }
        }
        return jumptimes;
    }
};