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

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

题目链接：122.买卖股票的最佳时机II

踩坑：差点陷入不必要的细节，比如怎么表现买入卖出，怎么体现同一天买入卖出

思路：这里的股票买卖是看了天眼，明天的涨跌今天就知道，那肯定是如果明天涨了我今天才买，因此，将每天的价格可视化出来，统计所有单调上升的总和即可。

代码：

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

LeetCode 55.跳跃游戏

题目链接：55.跳跃游戏

踩坑：不需要去纠结具体的跳跃路径，只要跳跃的范围能覆盖到结尾即可。

思路：每一个元素的值与其索引的和就是它能到达的最大索引，因此以能到达的最大索引为右边界，同时也不断维护最大索引即可。

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

LeetCode 45.跳跃游戏II

题目链接：45.跳跃游戏II

踩坑：无

思路：在确定当前最大覆盖范围后，向前遍历并不断维护今后能达到的最大范围直到遍历完当前最大范围，之后判断今后的最大范围能不能包含结尾，如果能则加一步即可完成任务，如果不能则加一步后更新最大覆盖范围继续遍历。

代码：

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