45. Jump Game II

https://leetcode.com/problems/jump-game-ii/

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

给定数组每个元素代表从当前点最远能跳多远，问最少跳几次能跳完整个数组。数组的每个元素决定了从当前点能最远跳到的地点，也就是一个window。在这个window里能到大的最远距离形成了下一个window的边界。window数目也就是最短需要的步数。因此用cur表示当前的window的边界，next表示下个window的极限位置。每次到达cur表示结束一个window。

/*
 * @lc app=leetcode id=45 lang=cpp
 *
 * [45] Jump Game II
 */
class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, cur = 0, next = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            next = max(next, i + nums[i]);
            if (i == cur) {
                cur = next;
                ++res;
            }
        }
        return res;
    }
};