45. Jumping game II

---

Topic link

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

---

One 、 Title Description

Here's an array of nonnegative integers nums , You are first in the array .

Each element in the array represents the maximum length you can jump at that location .

Your goal is to reach the last position of the array with the least number of jumps .

Suppose you can always reach the last position of the array .

• Example 1:

Input : nums = [2,3,1,1,4]
Output : 2
explain : The minimum number of jumps to the last position is 2.
From the subscript for 0 Jump to subscript 1 The location of , jump 1 Step , Then jump 3 Step to the last position of the array .

• Example 2:

Input : nums = [2,3,0,1,4]
Output : 2

• Tips :

1 <= nums.length <= 104
0 <= nums[i] <= 1000

---

Two 、 Ideas

1. Greedy solution

The key point is to see the maximum coverage .
Greedy thinking , Local optimum ： At present, you can move as much as possible , If you haven't reached the end , Step number plus one . The overall best ： Take as many steps as possible , So as to achieve the minimum number of steps .
Start with coverage , No matter how you jump , It must be possible to jump within the coverage , Increase coverage with minimum steps , Once the coverage covers the end point , The result is the minimum number of steps ！
Here we need to count two coverage areas , The maximum coverage of the current step and the maximum coverage of the next step .
If the moving subscript reaches the maximum coverage distance of the current step , If you haven't reached the end , Then we must take another step to increase the coverage , Until the coverage covers the end .

There is still a special case to consider , When the moving subscript reaches the longest subscript currently covered

• If the longest subscript is currently covered No Set end point , Just add one step , We need to keep going .
• If the longest subscript is currently covered Namely Set end point , You don't have to add one step , Because you can't go back .

class Solution {
    
public:
    int jump(vector<int>& nums) {
    
        if (nums.size() == 1) return 0;
        int curDistance = 0;    //  Currently covering the longest subscript 
        int result = 0;            //  Record the maximum number of steps taken 
        int nextDistance = 0;   //  Next, cover the longest subscript 
        for (int i = 0; i < nums.size(); i++) {
    
            nextDistance = max(nums[i] + i, nextDistance);  //  Update the next step to cover the longest subscript 
            if (i == curDistance) {
                             //  Encountered the longest subscript of the current coverage 
                if (curDistance != nums.size() - 1) {
           //  If the longest distance currently covered is not the end point 
                    result++;                                  //  Need to take the next step 
                    curDistance = nextDistance;             //  Update the current overlay longest subscript （ Equivalent to refueling ）
                    if (nextDistance >= nums.size() - 1) break; //  The coverage of the next step can reach the end , End of cycle 
                } else break;                               //  The longest subscript of the current coverage is the end of the collection , Don't do it ans++ Operation , End directly 
            }
        }
        return result;
    }
};

Time complexity ：O(n)
Spatial complexity ：O(1)

---

summary

Topic The key lie in ： Increase the maximum coverage with the minimum number of steps , Until the coverage covers the end , The minimum number of steps in this range must jump to , No matter how you jump , Don't worry about whether to jump one unit or two units in one step .