45. 跳跃游戏 II

题目描述：

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

示例:

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

说明:

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

解题思路：

1）、首先是可以看出每次是寻找i == midMax范围内最大的可以扩展到的位置， 2）、midMax更新为每个节点i == midMax最大扩展到的位置； 3）、跳到下一个midMax则ret++,直到 midMax + 1 >= nums.size() , + 1是因为 i是从0开始的；

例子： nums = [2,3,1,1,4]

1)、midMax = 0 ， ret = 0 ； 当 i = 0； tmp = 0 + nums[0] = 2; 2)、miMax = 0; i == miMax ；miMax = tmp = 2 ；ret = 1 ; 当 i = 1； tmp = max(1 + nums[1], tmp) = 4; 当 i = 2； tmp = max(2 + nums[2], tmp) = max(3, 4) = 4; 3)、 miMax = 2; i == miMax ；miMax = tmp = 4 ；ret = 2 ; 又因为if(miMax + 1 = nums.size()) 所以：break ;

代码实现：

class Solution { public: int jump(vector<int>& nums) { int ret = 0 ,midMax = 0 , tmp = 0 , i ; for (i = 0 ; i < nums.size() ; i ++) { //tmp：记录当前位置可以跳到的最大位置； tmp = max(tmp , i + nums[i]) ; //更新 midMax ； 跳到下一个 midMax 故 ret ++ ； if (i == midMax) { if (midMax + 1 >= nums.size()) break ; ret ++ ; midMax = tmp ; } } return ret ; } };

复杂度计算：

时间复杂度：O（n） ； 空间复杂度：O（1）；