Leetcode第45题(跳跃游戏II)

题目描述:

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

示例 1: 输入: nums = [2,3,1,1,4] 输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2: 输入: nums = [2,3,0,1,4] 输出: 2

使用 i 遍历数组，每次维护一个从当前位置所能走到的最远位置的区域，当 i 为 0 时，maxPos所能到达的最远下标maxPos = max(0,nums[0] + 0) = 2，当 i == rightPos时，表示 i 已经走到了一步能走到的最远处，此时需要走到下一个区域，因此步数stepAns++，同时更新右边界rightPos = maxPos = 2。

当 i 为 2 时，maxPos所能到达的最远下标maxPos = max(4,nums[2] + 2) = 4，当 i == rightPos时，表示 i 已经走到了一步能走到的最远处，此时需要走到下一个区域，因此步数stepAns++，同时更新右边界rightPos = maxPos = 4。

当 i 为 4 时，maxPos所能到达的最远下标maxPos = max(5,nums[4] + 4) = 8，当 i == rightPos时，表示 i 已经走到了一步能走到的最远处，此时需要走到下一个区域，因此步数stepAns++，同时更新右边界rightPos = maxPos = 8。 因此stepAns值为3, 即为走到数组尾的最少步数。

class Solution {
public:
    int jump(vector<int>& nums) {
        //maxPos当前所能到达的最远下标
        //rightPos右边界
        int maxPos = 0, rightPos = 0;
        int stepAns = 0;
        for(int i = 0;i < nums.size() - 1;i++){
            //更新当前所能到达的最远下标
            maxPos = max(maxPos,nums[i] + i);
            if(i == rightPos){
                rightPos = maxPos; //更新右边界
                stepAns++;
            }
        } 
        return stepAns;
    }
};