55. 跳跃游戏
题目描述
输入一个非负整数数组 nums。开始时你站在下标 0。
站在下标 i 时，你可以向后跳 0 到 nums[i] 步中的任意步数。
如果有办法跳到最后一个下标，返回 true；否则返回 false。
示例 1
输入：nums = [2,3,1,1,4] 输出：true
解释：从下标 0 跳 1 步到下标 1，再跳 3 步就到了末尾。
示例 2
输入：nums = [3,2,1,0,4] 输出：false
解释：不管怎么跳都会停在下标 3，而那里只能跳 0 步，到不了末尾。
数据范围
1 <= nums.length <= 10^40 <= nums[i] <= 10^5
解题思路：贪心（最远可达）
从左到右维护当前能到达的最远位置；若当前位置超过它则失败。
为什么正确
遍历前的 farthest 表示已处理位置能覆盖的最右边界。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
不能只看当前位置的跳数，必须保留之前所有位置产生的最远边界。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return Trueclass Solution {
public boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest)
return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
}class Solution {
public:
bool canJump(vector<int>& nums) {
int farthest = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > farthest)
return false;
farthest = max(farthest, i + nums[i]);
}
return true;
}
};func canJump(nums []int) bool {
farthest := 0
for i, jump := range nums {
if i > farthest {
return false
}
farthest = max(farthest, i+jump)
}
return true
}var canJump = function(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest)
return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
};function canJump(nums: number[]): boolean {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest)
return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
};其他解法
正向贪心维护最远可达位置，可以提前结束；逆向贪心维护能到终点的最左位置，两者都是一次遍历、常数空间。
解法 2：逆向贪心 时间 O(n)，空间 O(1)
用 last 表示目前已知能到达终点的最左下标，初始为 n - 1。从 n - 2 向左扫描，若 i + nums[i] >= last，说明从 i 能跳到一个能到终点的位置，令 last = i。扫描结束后判断 last 是否为 0。
和正向贪心复杂度相同。它从“终点能被谁到达”的角度思考，正确性更容易论证，但不能在中途提前返回 False。
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
last = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= last:
last = i
return last == 0class Solution {
public boolean canJump(int[] nums) {
int last = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= last) last = i;
}
return last == 0;
}
}class Solution {
public:
bool canJump(vector<int>& nums) {
int last = nums.size() - 1;
for (int i = (int)nums.size() - 2; i >= 0; i--) {
if (i + nums[i] >= last) last = i;
}
return last == 0;
}
};func canJump(nums []int) bool {
last := len(nums) - 1
for i := len(nums) - 2; i >= 0; i-- {
if i+nums[i] >= last {
last = i
}
}
return last == 0
}var canJump = function(nums) {
let last = nums.length - 1;
for (let i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= last) last = i;
}
return last === 0;
};function canJump(nums: number[]): boolean {
let last = nums.length - 1;
for (let i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= last) last = i;
}
return last === 0;
}