算法：贪心---跳一跳

古城微笑少年丶 2024-03-03 08:09 112阅读 0赞

![在这里插入图片描述][dd252908e61c4310b41522b55aa993f0.png_pic_center]

#### 1、题目： ####

给你一个非负整数数组 `nums` ，你最初位于数组的 **第一个下标** 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 `true` ；否则，返回 `false` 。

#### 2、分析特点： ####

*  题目要求：你最初位于数组的 **第一个下标** ，判断你是否能够到达最后一个下标 ==> 思维转换：如果我已经到了倒数最后一个位置，到了倒数第二个位置。。。

> 当然想正着理解也可以：
> 
> 设想一下，对于数组中的任意一个位置 yyy，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums\[x\]，这个值大于等于 y，即 x+nums\[x\]≥y，那么位置 y 也可以到达。
> 
> 换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯ ,x+nums\[x\] 这些连续的位置都可以到达。
> 
> 这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums\[x\] 更新最远可以到达的位置。
> 
> 在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

#### 3、思路： ####

从终点开始算，判断终点之前是否有位置能到达终点。有，就将当前点当做终点；无，则继续向前判断。当终点与起点重合时，则能从起点跳到终点。

#### 4、代码： ####

public boolean canJump(int[] nums) {
        
    		if(nums.length == 1) return true 
    		let len=nums.length-1
    		for(let i = nums.length-2;i>= 0;i--){
        
     		   if(nums[i] >= len-i){
        
            		len = i;
        		}
    		}
    		return len == 0;
        }

#### 5、复杂度分析： ####

>  *  时间复杂度：O(n)，其中 nnn 为数组的大小。只需要访问 nums 数组一遍，共 nnn 个位置。
>  *  空间复杂度：O(1)，不需要额外的空间开销。

#### 6、总结： ####

从终点开始算，判断终点之前是否有位置能到达终点。有，就将当前点当做终点；无，则继续向前判断。当终点与起点重合时，则能从起点跳到终点。

**如果本文对你有帮助的话记得给一乐点个赞哦，感谢！**

[dd252908e61c4310b41522b55aa993f0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/b174c42622164a89bd7837f3fe32ac5e.png