LeetCode 题解工作台
跳跃游戏 VI
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。 你的目标是到达数组最后一个位置（下标…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示到达下标 的最大得分，那么 的值可以从 转移而来，其中 满足 $i - k \leq j \leq i - 1$。因此我们可以使用动态规划求解。 状态转移方程为：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例 1：
输入：nums = [1,-1,-2,4,-7,3], k = 2 输出：7 解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：
输入：nums = [10,-5,-2,4,0,3], k = 3 输出：17 解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：
输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出：0
提示：
-
1 <= nums.length, k <= 105 -104 <= nums[i] <= 104
解题思路
方法一：动态规划 + 单调队列优化
我们定义 表示到达下标 的最大得分，那么 的值可以从 转移而来，其中 满足 。因此我们可以使用动态规划求解。
状态转移方程为：
我们可以使用单调队列优化状态转移方程，具体做法是维护一个单调递减的队列，队列中存储的是下标 ，并且队列中的下标对应的 值是单调递减的。在进行状态转移时，我们只需要取出队首的下标 ，即可得到 的最大值，然后将 的值更新为 即可。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
n = len(nums)
f = [0] * n
q = deque([0])
for i in range(n):
if i - q[0] > k:
q.popleft()
f[i] = nums[i] + f[q[0]]
while q and f[q[-1]] <= f[i]:
q.pop()
q.append(i)
return f[-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on sliding window maximum optimization for dynamic programming.
- question_mark
Expect explanation of deque usage to avoid redundant max calculations.
- question_mark
Be ready to discuss edge cases with negative numbers and small k values.
常见陷阱
外企场景- error
Using simple nested loops without deque causes timeouts for large arrays.
- error
Forgetting to remove indices outside the k-range from the deque.
- error
Confusing dp[i] as max score from start instead of from current index.
进阶变体
外企场景- arrow_right_alt
Jump Game VI with varying k per index, requiring dynamic window adjustments.
- arrow_right_alt
Minimizing the score instead of maximizing, changing deque logic accordingly.
- arrow_right_alt
Allowing backward jumps up to k steps, adding bidirectional state management.