leetcode：45. Jumping game II [classic greed]

analysis

We have reached the last （ You can play jump games 1 Judge ）
And then we still follow the interval we can walk each time , Record maxPos
Traverse the positions one by one , Walk and look in the area where you can walk to find the next one maxPos
Then if the current position i touch end（ That's the last one maxPos The location of , This is the limit we can go ）
Now step Must be added 1, And the next one end Is what we currently record maxPos
The most greedy way

ac code

class Solution:
    def jump(self, nums: List[int]) -> int:

        #  You can play jump games 1 To determine whether the last position can be reached 
        #  This jumping game 2 be based on 1 Find the minimum number of arrivals 
        #  Or greedy , Current [cur, maxPos] look forward , Only those who can go the farthest “ come on. ”

        maxPos, mustAdd, step = 0, 0, 0
        n = len(nums)

        #  Do not refuel until you reach the place where you must refuel 
        #  The last position is to reach , No need to refuel 
        for i in range(n - 1):
            #  Greedy is the farthest position you can see in the current range 
            maxPos = max(maxPos, nums[i] + i)
            #  If you go to a place where you must refuel 
            if i == mustAdd:
                #  The place that must be refueled next time 
                #  It is the farthest place you can see in the last section 
                mustAdd = maxPos
                step += 1
        
        return step

summary

Go through all the ranges that the current fuel volume can support
Then go to each position and look at it while walking , If you refuel at this position, the next maximum position you can reach
Then find the next interval in this interval maxPos that will do