day32 贪心（2）

day32
代码随想录
2023.12.30

1.122买卖股票的最佳时机
这道题，真的忽悠人啊，题感觉很难得样子，有点不知道怎么写，看了文字讲解，发现好有道理。其实主要就是一个分解的思想很难想象。就是如果第一天买的，第三天卖掉，可以看作第一天买，第二天卖掉，与第二天买与第三天卖。就将一个大范围分解为两天两天的，虽然题目写每一天只能买或者卖，但思路是可以变变通得，要是明白这个拆分思想，那做法就变得清晰起来了，计算每两天得分解结果，因为只能持有一张股票，所以分解得就可以看作最后的选择，又要最大利润，那就所有正数之和喽，解法不就出来了！

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

2. 55跳跃游戏
这道题，虽然没看出来贪心得点在哪，但明白了一句话，“贪心要么简单，要么打死都不会”，这题就是，硬看半天没思路，讲解一看，有感觉好简单，总结就一句话，只要从当前位置（下标）走最大范围得距离能到最后，那就能跳过去。

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 = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};

3. 45跳跃游戏Ⅱ
看完讲解后感觉跟那个摇摆队列思路有点点的像呢，局部最优就是遍历在最好的情况下在更新参数，对于这道题就是，如果该部得最大范围不能到终点时，我在走一步，有点“能不走就不走得意思”，遍历到上一步得最大位置了，我在考虑下一步怎么走。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }
};