LeetCode #45：Jump Game II(跳跃游戏II)

题目描述

本题的思路与 #55 类似，也是需要选择最远的跳跃长度，区别是本题一定能跳到最后。我们设置变量 curCover，代表当前跳跃轮次可以跳到的范围 [0…curCover]；设置变量 nextCover，代表下一轮次可以跳到的范围 [0…nextCover]，在范围 [0…curCover] 中尝试找出 nextCover 的最大值。

若 curCover 值为终点值，说明本轮跳跃后就能到达终点，否则至少需要再跳一次，跳跃轮次须 +1。

本题贪心就贪在：我们若要使得到达终点步数最少，那每一步我们都尽可能走的远。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) // 只有一个元素，那不用跳就能到终点
            return 0;
        
        int res = 1; // 若有两个以上的元素，至少要跳一次才能到终点
        int curCover = nums[0];
        int nextCover = nums[0];
        for(int i = 1; i < n; i ++) { //循环从下标1开始
            nextCover = max(nextCover, i + nums[i]); // 尝试寻找最大的下一跳
            if(i == curCover) { // 遇到了当前轮次的最大下标
                if(curCover != n - 1) { // 如果当前轮次最大下标不是末尾元素，说明至少还要跳一轮
                    res ++; // 轮次+1
                    curCover = nextCover; // 更新覆盖范围（进入下一轮）
                    if(nextCover >= n - 1) // 如果下一轮的最大下标已经覆盖了末尾元素，说明已经到达终点
                        break;
                } else { // 当前轮次的最大下标已经抵达终点，直接结束
                    break;
                }
            }
        }

        return res;
    }
};

针对上面 “遇到当前轮次的最大下标” 的控制逻辑，我们可以尝试进行优化：i 只要等于当前轮次的最大下标，res 直接 +1，不用考虑终点的处理；同时将 i 的循环范围改为 i < n-1（即 i <= n-2）。

当 i = n-2时，如果 i == curCover，需要再走一步才能到达末尾（题目假设一定能到末尾）；如果 i ≠ curCover，说明 curCover已经覆盖了末尾，不用再走下一轮。这种策略变相实现了终点处理的逻辑。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)
            return 0;
        
        int res = 1;
        int curCover = nums[0];
        int nextCover = nums[0];
        for(int i = 1; i < n - 1; i ++) {
            nextCover = max(nextCover, i + nums[i]);
            if(i == curCover) {
                res ++;
                curCover = nextCover;
            }
        }

        return res;
    }
};