How does the greedy approach solve Jump Game II?

The greedy approach in Jump Game II works by choosing the farthest reachable index at each step, ensuring that we minimize the number of jumps needed to reach the last index.

What is the time complexity of the optimal solution for Jump Game II?

The time complexity of the optimal solution is O(n), where n is the length of the array. This is achieved by processing each index once.

Why is dynamic programming used in Jump Game II?

Dynamic programming is used in Jump Game II to track the minimum jumps required to reach each index and efficiently calculate the optimal path to the end.

What are the edge cases in Jump Game II?

Edge cases include small arrays, such as those with only one element, and arrays with large jump values. Handling these ensures the solution works for all inputs.

How does state transition help in Jump Game II?

State transition in Jump Game II helps by tracking reachable indices and dynamically updating the minimum jumps, optimizing the process of reaching the last index.

#45

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums 。初始位置在下标 0。每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处： 0 且 i + j 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - …

数组动态规划贪心

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
题目保证可以到达 n - 1

lightbulb

解题思路

方法一：贪心

我们可以用变量 $mx$ 记录当前位置能够到达的最远位置，用变量 $last$ 记录上一次跳跃到的位置，用变量 $ans$ 记录跳跃的次数。

接下来，我们遍历 $[0,..n - 2]$ 的每一个位置 $i$ ，对于每一个位置 $i$ ，我们可以通过 $i + nums[i]$ 计算出当前位置能够到达的最远位置，我们用 $mx$ 来记录这个最远位置，即 $mx = max(mx, i + nums[i])$ 。接下来，判断当前位置是否到达了上一次跳跃的边界，即 $i = last$ ，如果到达了，那么我们就需要进行一次跳跃，将 $last$ 更新为 $mx$ ，并且将跳跃次数 $ans$ 增加 $1$ 。

最后，我们返回跳跃的次数 $ans$ 即可。

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

相似题目：

1

2

3

4

5

6

7

8

9

10

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = mx = last = 0
        for i, x in enumerate(nums[:-1]):
            mx = max(mx, i + x)
            if last == i:
                ans += 1
                last = mx
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Can you describe how the greedy approach minimizes the number of jumps?
question_mark
Do you understand how state transitions optimize the solution in Jump Game II?
question_mark
Are you able to efficiently implement a solution with a time complexity of O(n)?

warning

常见陷阱

外企场景

error
A common pitfall is not updating the farthest reachable index correctly, which can result in missed opportunities to minimize jumps.
error
Failing to handle edge cases, such as when the array has only one element, can cause incorrect jump calculations.
error
Using a brute force solution instead of greedy or dynamic programming can lead to inefficient performance, especially for large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Jump Game I - Minimum Jumps with no backtracking.
arrow_right_alt
Jump Game III - Adding obstacles and varying jump limits.
arrow_right_alt
Jump Game IV - Multi-dimensional arrays with jumps.

help

常见问题

外企场景

继续练习

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