当前位置：首页 > news >正文

【LeetCode: 跳跃游戏】贪心算法

news 2026/4/28 6:14:33

目录

一、题目描述

二、题目解答

2.1 思路

2.2 代码

三、总结

一、题目描述

给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。

示例 1：输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。

二、题目解答

2.1 思路

最开始一看到题目就直接简单的想这不就遍历数组，遇到 0 就返回 false 就好了啊。但结果emm也是大错特错了。😢因为如果 0 前面的数字可以直接越过 0 呢？那不也能跳过去！所以我们要考虑到当前元素能跳跃到最远的元素下标为多少。

思路：1. 定义一个变量 maxJump，表示当前能达到的最远下标，初始值为 0

2. 遍历数组，若 i > maxJump，就说明该元素连当前位置都到达不了，所以直接返回false；否则就更新 maxJump 的值；最后对 maxJump 与数组最后一个元素下标比较，若大于等于就返回 true

3. 遍历结束，返回 true

接下来想说一下这个 maxJump 的值该怎样更新？我们知道 maxJump 表示的是最远下标，那么当我们更新 maxJump 时就不能只是把 nums[i] 和当前 maxJump 它俩之间取最大值！我们应该加上当前元素的下标，因为是从当前元素开始跳的，如果不加的话都默认是从 0 开始跳的了😁！我觉得这是一个很容易落下的点。

2.2 代码

class Solution { public boolean canJump(int[] nums) { int maxJump = 0; int n = nums.length; for(int i = 0; i < n; i++){ if(i > maxJump){ return false; }else{ maxJump = Math.max(i + nums[i],maxJump); } if(maxJump >= n-1){ return true; } } return true; } }