Greed 45. Jumping game II

1 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 .

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

2 Title Example

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

3 Topic tips

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000

4 Ideas

This problem is a typical greedy algorithm , The global optimal solution is obtained through the local optimal solution .
Method 1 ：
Our goal is to reach the last position of the array , So we can consider the last — The position before the jump , This position can reach the last position by jumping .
If there are multiple positions, you can reach the last position by jumping , So how should we choose ? intuitively , We can 「 greedy 」 Choose the location farthest from the last location , That is, the position corresponding to the smallest subscript . therefore , We can traverse the array from left to right , Select the first location that meets the requirements .
Find the last — After the position before the jump , We continue to greedily look for the position before the penultimate jump , And so on , Until you find the beginning of the array .

Method 1 is intuitive , But the time complexity is high , Is there any way to reduce the time complexity ?
If we 「 greedy 」 Forward lookup , Find the farthest reachable position every time , You can get the least number of jumps in linear time .
for example , For arrays [2,3,1,2,4,2,3], The initial position is the subscript 0, From the subscript О set out , The longest reachable subscript 2. Subscript 0 In an accessible location , Subscript 1 The value of is 3, From the subscript 1 You can go further , So the first step is to reach the subscript 1.
From the subscript 1 set out , The longest reachable subscript 4. Subscript 1 In an accessible location , Subscript 4 The value of is 4, From the subscript 4 You can go further , So the second step reaches the subscript 4.
In the concrete realization , We maintain the maximum subscript position currently reachable , Mark as boundary . We traverse the array from left to right , When we reach the border , Update the boundary and increase the number of jumps 1.
When you go through groups , We don't access the last element , This is because before accessing the last element , Our boundary must be greater than or equal to the last position , Otherwise you can't jump to the last position . If you access the last element , When the boundary is exactly the last position , We'll add one 「 Number of unnecessary jumps 」, So we don't have to access the last element .

5 My answer

class Solution {
    
    public int jump(int[] nums) {
    
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
    
            for (int i = 0; i < position; i++) {
    
                if (i + nums[i] >= position) {
    
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

class Solution {
    
    public int jump(int[] nums) {
    
        int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
    
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
    
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}