LeetCode高频题55加类似新题45：跳跃游戏 II：最少需要跳多少步才能抵达终点

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

基础知识：
【1】LeetCode高频题55. 跳跃游戏

本题！是互联网大厂考过的笔试原题，202204月的笔试，好像是京东还是字节考的，我忘了
本题！是互联网大厂考过的笔试原题，202204月的笔试，好像是京东还是字节考的，我忘了
本题！是互联网大厂考过的笔试原题，202204月的笔试，好像是京东还是字节考的，我忘了

---

文章目录

• LeetCode高频题55加类似新题45：跳跃游戏 II：最少需要跳多少步才能抵达终点
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 再用一个例子理解一下：
• 总结

题目

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

一、审题

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

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

示例：

你从i=0出发，可以跳1步去1位置，也可以跳2步去7，
从1位置，如果每次跳1步，那你就跳太多了

但是跳到7，一下子去N-1，就只需要2步
这就是最少的步数！！！

---

二、解题

最少需要跳多少步才能抵达终点？
上文咱们讲过本题的思路

再来回顾一下：
给你一个arr，在i位置，arr[i]是你可以从i跳最多的步骤数，比如0,1,2，arr[i]步
问你，从0出发，到N-1，请问最少可以跳多少步抵达终点？？？？

跟基础知识：
【1】LeetCode高频题55. 跳跃游戏
不一样哦

咱们这次要求最少的步数

这题设置几个变量
step：当前最少跳step步能到i位置
cur：step步内最远右边界
next：step+1步，下一次最远右边界

开始倒腾：
step：当前最少跳step步能到i位置，最开始只跳0步，原本就在i=0位置
cur：step步内最远右边界，cur=0，当前不跳只能在i=0处，下一次呢？
next：step+1=1步，下一次最远右边界，在i=0位置，多跳一步，next可以取i+[i]=3
起初：

来到i=1时，因为i>cur，所以需要step增加1步，这是必须的！
step：当前最少跳step步能到i位置，step=1，上次说过next在step=1时最远右边界，此刻step=1，所以呢cur=next，更新一下
cur：step=1步内最远右边界，cur=next=3
next：step+1=2步，即下一次最远右边界，next可以取i+[i]=1+1=2？不，没有原来那个next=3大哦！不更新，所以next=3

来到i=2时，因为i<=cur=3，所以需要step不需要增加步数，因为我可以少跳一点就来2位置了，还用不着更新step！
step：当前最少跳step步能到i位置，step=1，不更新
cur：step=1步内最远右边界，cur=3，不动，这个是看step新增时，我才将next更新给cur的
next：step+1=2步，即下一次最远右边界，next可以取i+[i]=2+7=9？9>next更新，所以next=9

来到i=3时，因为3=i<=cur=3，所以需要step不需要增加步数，因为我可以少跳一点就来3位置了，还用不着更新step！
step：当前最少跳step步能到i位置，step=1，不更新
cur：step=1步内最远右边界，cur=3，不动，这个是看step新增时，我才将next更新给cur的
next：step+1=2步，即下一次最远右边界，next可以取i+[i]=3+1=4？<next=9，不需要更新，所以next=9

来到i=4时，因为4=i>cur=3，所以需要step必须需要增加1步，更新step！
step：当前最少跳step步能到i位置，step=2，
cur：step=2步内最远右边界，cur=next=9，更新哦，这个是看step新增时，我才将next更新给cur的
next：step+1=3步，即下一次最远右边界，next可以取i+[i]=6+3=6？<next=9，不需要更新，所以next=9

实际上，从此往后，step，都只是2，cur=9很大，你咋着i<=cur，
next在i=8时，可以更新next=10
但是step内，我们的cur=9，i=9时，已经到了最右边界了
此时step=2就是咱们的最少必须跳的步数

中间用cur来控制，我其实选择跳所有位置i，都能卡住一个最右右边界，当cur无法到i，就要增加步数
而下一次多增加一步，我能最远到哪里，更新给next，这个next就是为每一次cur做准备的

再用一个例子理解一下：

总之，条件就是
i>cur,step必须增加步数，更新next给cur
next是之前每一次来到i，更新的i+[i]，就是从i能到的最远右边界
当i<=cur,step不管，cur不管，但是看看next可能会不会跳更远？更新一下

目的就是通过i和cur的关系，确定step到底要不要增加步数，然后用next准备给cur更新step内的最远右边界

手撕代码：

class Solution {
    public int jump(int[] nums) {
         if (nums == null || nums.length < 2) return 0;//只需要0步即可
        int N = nums.length;

        //否则就看仨变量了
        int step = 0;//目前跳0步
        int cur = 0;//跳step步能最远到哪？
        int next = nums[0];//如果step+1步，能最远到哪？？

        for (int i = 0; i < N; i++) {
            //i>cur,step必须增加步数，更新next给cur
            if (i > cur){
                step++;
                cur = next;//增加了步数，next更新给它cur
            }
            //next是之前每一次来到i，更新的i+[i]，就是从i能到的最远右边界
            //当i<=cur,step不管，cur不管，但是看看next可能会不会跳更远？更新一下
            //任何时候来到i都要更新next
            next = Math.max(next, i + nums[i]);//这个变量很巧，记住了
        }

        //最后能到i，搞完step就是最少的
        return step;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

LeetCode测试：


绝对的牛
这题跟LeetCode那个能否跳到最右边界那时，就很相似
后来很多互联网大厂都改编拿来考过的，笔试

---

总结

提示：重要经验：

1）这类题目，来到i，能到最远的右边界next=i+[i]，这点是要搞清楚的，不管啥跳跃游戏，至于增加不增加步数，看看i和当前step步内能到的最远又边界cur的关系，i>cur，step++，cur=next，而每次都要把i+[i]更新给next
2）在跳跃游戏第一题中，当时的cur每次都要将i+[i]更新给它，i>cur就无法抵达最右边界。这个题互联网大厂直接考笔试原题了
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。