45. 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
思路：
找此跳范围内，可以跳到最远地方的下一个位置

class Solution {
public:
    int jump(vector<int>& nums) {
        const int len=nums.size();

        if(len<=1){
            return 0;
        }

        map<int,int> p;
        p[0]=nums[0];
        int count=0;
 
        for(int i=0;i<len;i++){
            if(p.begin()->second+p.begin()->first>=len-1){
                return count+1;
            }

            int max_remain=-1;
            int max_index=0;
            for(int j=1;j<=p.begin()->second;j++){
                int index=p.begin()->first+j;
                int expect=nums[index]+j;
                if(expect>max_remain){
                    max_remain=expect;
                    max_index=index;
                }
            }
            if(max_remain==-1){
                return -1;
            }
            else{
                p.clear();
                p[max_index]=nums[max_index];
                count++;
            }
        }

        return -2;
    }
};

原文地址：http://www.cnblogs.com/imreW/p/16868804.html