本文共 1210 字，大约阅读时间需要 4 分钟。

题目描述：

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

数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [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
   
    & 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）；

转载地址：http://xraei.baihongyu.com/