【力扣】[数组] 45.跳跃游戏||

1、题目

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

链接：https://leetcode-cn.com/problems/jump-game-ii

 

2、思路分析

1）正向查找可到达的最大位置
查找当前位置可以到达的最大位置，然后在这个区间之内，寻找最大的可达位置。

这里采用maxPos表示走到的最远位置，end表示上一次的位置，当i到达上一次位置时，step++，更新end，之后就进入循环，更新maxPos的最远位置。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int maxPos = 0, end = 0, step = 0;

        for(int i = 0; i < n - 1; ++i){
            if(maxPos >= i){ // maxPos下标操作，表示每次走过的位置的下标
                maxPos = max(maxPos, i + nums[i]);
                if(i == end){ // end表示上一次maxPos的位置，当i==end时，表示i刚走到上一次maxPos走过的位置，更新end的位置，step+1
                    end = maxPos;
                    ++step;
                }
            }
        }
        return step;
    }
};