Leetcode 45 Jumping game II (2022.02.14)

  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 <= 10⁴
0 <= nums[i] <= 1000

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/jump-game-ii

Method 1 ： Greedy Algorithm

C++ Submission ：

class Solution {
    
public:
    int jump(vector<int>& nums)
    {
    
        int ans = 0;
        int end = 0;
        int maxPos = 0;
        for (int i = 0; i < nums.size() - 1; i++)
        {
    
            maxPos = max(nums[i] + i, maxPos);
            if (i == end)
            {
    
                end = maxPos;
                ans++;
            }
        }
        return ans;
    }
};