西安市网站建设_网站建设公司_VPS_seo优化

一、读题

题目来源：https://leetcode.cn/problems/jump-game/

题目也是很好理解啊，就是根据数组里每一位的数值来判断是否可以走到结尾，并且每一位数值不是都要走完，可以只走一步，数值是可移动的最大步数。

二、示例讲解

实例1：[2,3,1,1,4]
我们最开始是在 nums[0] 的位置，那么我们接下来可以移动的步数最大是 2 我们可以选择走最大值直接走到nums[2]的位置，这个时候我们可以移动的步数最大值是 1 ，那么我们移动一步走到nums[3]，这个时候我们可以移动的步数最大值是 1 ，接下来只需要移动一步我们就走到了数组的最后一位，结束

示例 2： [3,2,1,0,4]
我们最开始是在 nums[0] 的位置，那么接下来我们可以走最大步数是 3 ，我们可以选择走3步，这个时候我们走到nums[3]，这个时候我们走不动了，当前运行我们移动的步数为0，说明这里是一个坑不给走了，那么我们重新来一次。

我们最开始是在 nums[0] 的位置，那么接下来我们可以走最大步数是 3 ，我们可以选择走2步，这个时候我们走到nums[2] ，这个时候我们可以移动的最大步数是 1 ，那么我们就移动一步来到nums[3]，这个时候我们又进入坑了，还是不行

我们最开始是在 nums[0] 的位置，那么接下来我们可以走最大步数是 3 ，我们可以选择走1步，这个时候我们走到nums[1] ，这个时候我们可以移动的最大步数是 2 ，那么我们就移动 1 步来到nums[2]，这个时候我们移动的步数最大值是1，还是会进入坑，那我们在nums[1]的时候移动 2 步，结果还是来到nums[3]还是走不通，所有方法都试过了，失败

三 、算法思路

比较难想，这是一个贪心的题目，贪心的题目有时候特别难想到，主包是研究了好久才理解的。

首先我们看题，我们的最终目的是需要到达数组的最后一个位置，那就意味着到达或者超过都算是到达。我们看数据范围，数组内的数值最小是0，那就是不存在往回移动的情况，那说明我们只有两种选择要么是往前移动，要么原地不动，原地不动结果就是失败，只要能够一直往前移动那么就绝对可以到达

也就是说只要我们不进入值为0的位置那么就没问题，我们根据这个思路我们想一想，开始遍历的时候，我拿到一个值，这个时候我们记录这个值为max（这个值表示当前能够移动到的最远位置），那么接下来我们往后移动又会得到一个值，我们将这个值加上当前的位置和之前记录的值相比较那个大我们就保存下来，只要在移动过程中能够一直保证max一直是大于或者等于当前的移动位置 i，那么说明没有问题

但是如果我们发现位置 i 移动到的位置大于max，那么说明在中间的时候就卡住了不能往后走了，那么就说明失败，当前的数组无法走到最后

max表示我们理论上可以移动到的最远位置，i 表示我们实际移动的位置（数组遍历的下标），如果实际移动的位置 大于 max理论上可以移动到的最远位置 ，那说明是不正确的，只有max能够到达的位置才是我们真正能到达的最远位置，如果说max都到不了的地方那么我们也是到不了的

我们看示例二，这一组数据的max是3，最远可以走到nums[3]，那么我最远可以走到的地方是3，但是结尾是4，能够走到吗？

我们再看看示例一，在nums[1]的位置的时候max是4（3 + 1），最远可以到达nums[4]，那么说明可以到达nums[4]也就是最后的位置。

大家好好理一理，理解max的意义，能够到达的最远位置，代码实现很简单没精神有点不太好理解

四、代码实现：

class Solution { public boolean canJump(int[] nums) { int max = 0;//记录可以到达的最远位置 for(int i = 0 ; i < nums.length ; i++) { if(i <= max) {//当前位置可以到达 max = Math.max(max, nums[i] + i); } else { //出现不可到达的 return false; } } return true; } }

各位佬，如果有什么更加高效的算法欢迎评论区讨论，指导一下主包进步，原诸君共勉