leetcode题解45：跳跃游戏 II

描述

分析

仔细想想，如果从当前位置\(i\)最远可以第\(i+k\)个位置，那么从当前位置跳到\(i+1\)到\(i+k\)位置的步数是一样的，比如nums=[2,3,1,1,4]，那么从\(i=0\)开始跳，最远可以跳跃到\(i+nums[i]=2\)个位置，即要到达3 1只需一步，那么写算法的时候，可以一次更新每个位置要达到的最小步数，但是显然可以继续优化；

有必要每次往后更新每个位置的步数吗？因为从位置0最远能跳到位置2，所以位置1,2都是1步到达，只有当超过位置2位置时，步数才去更新（+1），这样就好了；

此时考虑另一个问题，到达位置1,2的最小步数确定了，那后面的位置怎么确定呢？显然是位置1,2之中能跳到的最远距离了，所以遍历时，还需要计算j+nums[j]的最大值，即跳2步能达到的最大距离，其中j是跳1步能达到的最远距离。

算法

首先令step为到达当前位置所需的步数，显然到达初始位置只需0步，从而设置初始step=0；令currReach为当前能达到的最远位置，显然设置初始currReach=0；令nextReach为下一个能达到的最远位置，同样初始nextReach=0；
遍历数组i in [0, n-1]
判断当前位置i是否超过了currReach，如果是，则执行第4步，否则执行第5步；
超过了，那么step=step+1，且currReach = nextReach，即当前能到达的最远距离更新为下一次能到达的最远距离；
没超过，继续找下一次能到达的最远距离，即更新nextReach = max(nextReach, i+nums[i])；
遍历结束，返回step

代码

c++

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int currReach = 0;
        int maxReach = 0;
        int step = 0;
        for (int i = 0; i < n; i++) {
            if (i > canReach) {
                step++;
                currReach = maxReach;
            }
            maxReach = maxReach > nums[i] + i ? maxReach : nums[i] + i;
        }
        return step;
    }
};