What is the time complexity of the Jump Game problem?

The time complexity for both the greedy and dynamic programming solutions is O(n), where `n` is the length of the input array.

How can I solve Jump Game using dynamic programming?

The dynamic programming approach involves iterating through the array in reverse, marking reachable indices, and checking if the start index is reachable.

Can the Jump Game problem be solved using a greedy approach?

Yes, the greedy approach solves Jump Game by keeping track of the farthest index reachable from each position and ensuring no position is unreachable.

What are common edge cases for the Jump Game problem?

Common edge cases include arrays with a single element, arrays with no valid jumps (e.g., `[3, 2, 1, 0, 4]`), and arrays where the first element is 0.

Why does the greedy approach for Jump Game work?

The greedy approach works because it iterates over the array, always ensuring the farthest reachable index is updated. If at any point we can’t reach the next position, we know we can't reach the last index.

#55

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。示例 1：输入： nums = [2,3,1,1,4] 输出： true 解释：可以先跳 …

数组动态规划贪心

题目描述

给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：贪心

我们用变量 $mx$ 维护当前能够到达的最远下标，初始时 $mx = 0$ 。

我们从左到右遍历数组，对于遍历到的每个位置 $i$ ，如果 $mx \lt i$ ，说明当前位置无法到达，直接返回 false。否则，我们可以通过跳跃从位置 $i$ 到达的最远位置为 $i+nums[i]$ ，我们用 $i+nums[i]$ 更新 $mx$ 的值，即 $mx = \max(mx, i + nums[i])$ 。

遍历结束，直接返回 true。

时间复杂度 $O(n)$ ，其中 $n$ 为数组的长度。空间复杂度 $O(1)$ 。

相似题目：

1

2

3

4

5

6

7

8

9

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        mx = 0
        for i, x in enumerate(nums):
            if mx < i:
                return False
            mx = max(mx, i + x)
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand the greedy approach for Jump Game and its benefits?
question_mark
Can you explain how the dynamic programming solution works and its space complexity?
question_mark
Will you be able to identify edge cases, such as when the array has only one element?

warning

常见陷阱

外企场景

error
Forgetting that you must update the farthest reachable index in the greedy approach.
error
Confusing the order of jumps in dynamic programming, which can lead to incorrect conclusions about reachability.
error
Misunderstanding edge cases, such as when the array has only one element or if it’s impossible to jump due to zeros in the array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Jump Game II: Minimum Jumps
arrow_right_alt
Jump Game III: Reachable Indices with Constraints
arrow_right_alt
Jump Game IV: Reaching Target with Optional Restrictions

help

常见问题

外企场景

继续练习

#45 跳跃游戏 II #122 买卖股票的最佳时机 II #376 摆动序列