55. Jumping game

---

Topic link

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

---

One 、 Title Description

Given an array of nonnegative integers nums , You're in the beginning of the array The first subscript .

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

Judge whether you can reach the last subscript .

• Example 1：

Input ：nums = [2,3,1,1,4]
Output ：true
explain ： You can jump first 1 Step , From the subscript 0 Reach subscript 1, And then from the subscript 1 jump 3 Step to the last subscript .

• Example 2：

Input ：nums = [3,2,1,0,4]
Output ：false
explain ： No matter what , Always arrive, subscript 3 The location of . But the maximum jump length of the subscript is 0 , So it's never possible to reach the last subscript .

• Tips ：

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

Two 、 Ideas

When I first saw this question, I might think ： If the current location element is 3, What on earth am I doing , Or two steps , Or three steps , How many steps is the best ？

In fact, it doesn't matter how many steps you take , The key is the coverage that can jump ！

You don't have to know exactly how many steps to jump at a time , Take the maximum number of jump steps each time , This is the coverage that can jump .

In this range , Never mind how you jump , You can jump over anyway .

Then this question turns into whether the jump coverage can cover the end point ！

Take the maximum number of jump steps per move （ Get maximum coverage ）, Every unit moved , Update the maximum coverage .

Greedy algorithm local optimal solution ： Take the maximum number of jump steps each time （ Take the maximum coverage ）, The global optimal solution ： Finally, the overall maximum coverage , See if we can reach the end .

The local optimum leads to the global optimum , No counterexample , Try greed ！

class Solution {
    
public:
    bool canJump(vector<int>& nums) {
    
        int cover = 0;
        if (nums.size() == 1) return true; //  There's only one element , It's about being able to get there 
        for (int i = 0; i <= cover; i++) {
     //  Notice that this is less than or equal to cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; //  It indicates that the end point can be covered 
        }
        return false;
    }
};

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

i Each move can only be made in cover Moving within the limits of , Every time you move an element ,cover Get the value of this element （ New coverage ） A supplement to , Give Way i Keep moving .

and cover Take only max( The range after the value of this element is supplemented , cover Scope of itself ).

If cover Greater than or equal to the end subscript , direct return true That's all right. .