算法训练营Day28 | leetcode 122.买卖股票的最佳时机II 55.跳跃游戏 45.跳跃游戏II

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

本题首先要清楚两点：

• 只有一只股票！
• 当前只有买股票或者卖股票的操作

想获得利润至少要两天为一个交易单元。

贪心算法

这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…循环反复。

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…(prices[1] - prices[0])。

如图:

Java

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

可以看出有时候，贪心往往比动态规划更巧妙，更好用，所以别小看了贪心算法。

55.跳跃游戏

思路

刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

Java

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length  == 1) return true;
        int cover = 0;
        for(int i = 0; i <= cover; i++) {
            cover = Math.max(cover, i + nums[i]);
            if(cover >= nums.length - 1) return true;
        }
        return false;
    }
}

1. 为什么是 i <= coverRange？

i <= coverRange 的目的是限制迭代的范围，即只处理在当前「覆盖范围内」的位置。原因如下：

• 覆盖范围的定义：coverRange 是当前能到达的最远位置。
• 迭代条件的含义：当遍历到某个位置 i 时，如果 i 已经超过了 coverRange（即 i > coverRange），说明从起点无法跳到位置 i，因此也不可能再向后推进，直接返回 false。

换句话说，i <= coverRange 确保我们只在能到达的位置范围内更新最远跳跃范围。

2.i + nums[i] 的意思是计算从当前位置 i 最远可以跳到的位置。

• i 是当前所在的位置索引。
• nums[i] 是当前位置 i 上的数值，表示你在这个位置最多可以跳跃的步数。
• i + nums[i] 就是从位置 i 最远可以到达的位置。

例子

假设 nums = [2, 3, 1, 1, 4]，逐步分析 i + nums[i] 的作用：

1. 第 0 步 (i = 0):
   • 当前 nums[0] = 2，所以从位置 0 最远可以跳到 0 + 2 = 2。
2. 第 1 步 (i = 1):
   • 当前 nums[1] = 3，所以从位置 1 最远可以跳到 1 + 3 = 4。
3. 第 2 步 (i = 2):
   • 当前 nums[2] = 1，所以从位置 2 最远可以跳到 2 + 1 = 3。

i + nums[i] 用于动态计算当前能到达的最大范围，以便更新 coverRange（当前覆盖范围）。

45.跳跃游戏II

思路

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

Java

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1 || nums.length == 0 || nums == null) return 0;
        int cur = 0; // 当前跳跃覆盖的最远位置
        int next = 0; // 下一次跳跃覆盖的最远位置
        int count = 0; // 跳跃次数
        for(int i = 0; i < nums.length; i++) {
            next = Math.max(next, i + nums[i]);
            if(i == cur) {
                if(cur != nums.length - 1) {
                    count++;
                    cur = next;
                    if(cur >= nums.length - 1) break;  // 如果已经可以到达终点，提前结束
                }else {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}