跳转至

45 跳跃游戏II

普通版

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int start = 0, end = start + 1;
        int ans = 0;
        while(end < n){
            int nextStep;
            for(int i = start; i < end; i++){
                nextStep = max(nextStep, i + nums[i]);
            }
            ans++;
            start = end;
            end = nextStep + 1;
        }
        return ans;
    }
};

优化版

在跳跃游戏中,我们的思路是:

  • 我们不确定给定nums[i] 需要走多少步才能到达最后一个元素
  • 为此,我们进行了问题转换,我们不需要知道走多少步,只需要更新最大到达范围maxPos,如果maxPos大于等于n - 1,说明能够到达n - 1

在跳跃游戏II中,我们仍然能仿照这个思路:

  • 如果当前maxPos没有覆盖n - 1,那我们跳跃一次
  • 如果maxPos大于等于n - 1,说明能够到达n - 1,不需要再跳跃

不同之处在于:跳跃游戏II默认我们能够到达最后一个元素,求跳跃次数

如何能让跳跃次数最大,我们只需要走到maxPos的时候再跳跃即可 -> 我们维护两个maxPos,一个表示当前能够到达的最大位置,另一个表示下一次能够到达的最大位置

这里需要特别注意的一点:跳跃游戏II默认我们能够到达最后一个元素,因此我们不需要遍历到 n -1个元素,因为在那之前,我们一定能让maxPos覆盖n - 1

如果包含了n - 1反而有可能让结果多加一次(end 刚好等于n - 1)

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int end = 0;
        int maxNextStep = 0;
        int step = 0;
        // 注意:i < n - 1 而不是i < n
        for (int i = 0; i < n - 1; i++) {
            // 这里不需要if判断了,因为题目说一定能到达n - 1
            maxNextStep = max(maxNextStep, i + nums[i]);
            if (i == end) {
                ++step;
                end = maxNextStep;
            }
                // 与跳跃游戏不同,这里不需要maxNextStep >= n - 1判断,因为我们知道一定能到达n - 1
                // 如果加了这个判断,表明我们已经知道覆盖范围大于n - 1了
                // 但是这时候i还没走到更新后的end,我们需要让i走到end之后让step加一
        }
        return step;
    }
};

好理解版

思路

class Solution {
public:
    int jump(vector<int>& nums) {
        int targetRight = nums.size() - 1;
        int curRight = 0;
        int nextRight = 0;
        int ans = 0;
        for(int i = 0; i < targetRight; i++){
            nextRight = max(nextRight, i + nums[i]);
            if(i == curRight){
                curRight = nextRight;
                ans++;
            }
        }
        return ans;
    }
};