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

LeetCode 1696. 跳跃游戏 VI（中等）

news 2025/5/29 11:56:44

题目描述

给你一个下标从 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 <= 10^5
-10^4 <= nums[i] <= 10^4

问题分析

这道题是跳跃游戏系列的第六题，与前面的题目相比有以下特点：

跳跃规则：从位置 i 可以跳到 [i+1, min(n-1, i+k)] 范围内的任意位置
目标：到达数组最后一个位置，并使得经过的所有数字之和最大
约束：必须从下标 0 开始，必须到达下标 n-1

这是一个典型的动态规划问题，但如果使用朴素的动态规划，时间复杂度会是 O(nk)，在给定的数据规模下可能会超时。因此，我们需要使用优化的方法。

解题思路

动态规划基本思路

定义 dp[i] 表示到达位置 i 的最大得分。

状态转移方程：

dp[i] = max(dp[j]) + nums[i]，其中 max(0, i-k) <= j < i

初始状态：dp[0] = nums[0]

最终答案：dp[n-1]

优化方法

朴素的动态规划需要对每个位置 i 遍历前面 k 个位置来找最大值，时间复杂度为 O(nk)。我们可以使用以下方法优化：

优先队列（堆）：维护一个最大堆，存储前面位置的 dp 值和对应的下标
单调队列：维护一个单调递减的双端队列，队首始终是当前窗口内的最大值

算法过程

以示例1为例：nums = [1,-1,-2,4,-7,3], k = 2

使用单调队列的执行过程：

初始化：
- dp[0] = 1
- 队列：[(1, 0)]
i = 1：
- 队首 (1, 0) 在范围内
- dp[1] = 1 + (-1) = 0
- 移除队尾小于等于0的元素：移除 (1, 0)
- 队列：[(0, 1)]
i = 2：
- 队首 (0, 1) 在范围内
- dp[2] = 0 + (-2) = -2
- 队列保持：[(0, 1), (-2, 2)]
i = 3：
- 队首 (0, 1) 在范围内
- dp[3] = 0 + 4 = 4
- 移除队尾所有小于等于4的元素：移除 (0, 1) 和 (-2, 2)
- 队列：[(4, 3)]
i = 4：
- 队首 (4, 3) 在范围内
- dp[4] = 4 + (-7) = -3
- 队列：[(4, 3), (-3, 4)]
i = 5：
- 队首 (4, 3) 在范围内
- dp[5] = 4 + 3 = 7
- 移除队尾所有小于等于7的元素：移除 (4, 3) 和 (-3, 4)
- 队列：[(7, 5)]

最终答案：dp[5] = 7

详细代码实现

Java 实现 - 优先队列

import java.util.*;class Solution {public int maxResult(int[] nums, int k) {int n = nums.length;int[] dp = new int[n];// 优先队列，存储 [得分, 下标]，按得分降序排列PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);// 初始状态dp[0] = nums[0];pq.offer(new int[]{dp[0], 0});for (int i = 1; i < n; i++) {// 移除超出跳跃范围的元素while (!pq.isEmpty() && pq.peek()[1] < i - k) {pq.poll();}// 计算当前位置的最大得分dp[i] = pq.peek()[0] + nums[i];// 将当前位置的得分加入优先队列pq.offer(new int[]{dp[i], i});}return dp[n - 1];}
}

C# 实现 - 优先队列

using System;
using System.Collections.Generic;public class Solution {public int MaxResult(int[] nums, int k) {int n = nums.Length;int[] dp = new int[n];// 使用SortedSet模拟优先队列，存储 (得分, 下标)var pq = new SortedSet<(int score, int index)>(Comparer<(int score, int index)>.Create((a, b) => {int cmp = b.score.CompareTo(a.score); // 按得分降序return cmp != 0 ? cmp : a.index.CompareTo(b.index); // 得分相同时按下标升序}));// 初始状态dp[0] = nums[0];pq.Add((dp[0], 0));for (int i = 1; i < n; i++) {// 移除超出跳跃范围的元素while (pq.Count > 0 && pq.Min.index < i - k) {pq.Remove(pq.Min);}// 计算当前位置的最大得分dp[i] = pq.Min.score + nums[i];// 将当前位置的得分加入集合pq.Add((dp[i], i));}return dp[n - 1];}
}

Java 实现 - 单调队列（最优解）

import java.util.*;class Solution {public int maxResult(int[] nums, int k) {int n = nums.length;int[] dp = new int[n];// 单调递减队列，存储 [得分, 下标]Deque<int[]> deque = new ArrayDeque<>();// 初始状态dp[0] = nums[0];deque.offerLast(new int[]{dp[0], 0});for (int i = 1; i < n; i++) {// 移除超出跳跃范围的元素while (!deque.isEmpty() && deque.peekFirst()[1] < i - k) {deque.pollFirst();}// 计算当前位置的最大得分（队首是最大值）dp[i] = deque.peekFirst()[0] + nums[i];// 维护单调递减性质：移除队尾所有小于等于当前得分的元素while (!deque.isEmpty() && deque.peekLast()[0] <= dp[i]) {deque.pollLast();}// 将当前位置的得分加入队列deque.offerLast(new int[]{dp[i], i});}return dp[n - 1];}
}

C# 实现 - 单调队列（最优解）

using System;
using System.Collections.Generic;public class Solution {public int MaxResult(int[] nums, int k) {int n = nums.Length;int[] dp = new int[n];// 单调递减队列，存储 (得分, 下标)var deque = new LinkedList<(int score, int index)>();// 初始状态dp[0] = nums[0];deque.AddLast((dp[0], 0));for (int i = 1; i < n; i++) {// 移除超出跳跃范围的元素while (deque.Count > 0 && deque.First.Value.index < i - k) {deque.RemoveFirst();}// 计算当前位置的最大得分（队首是最大值）dp[i] = deque.First.Value.score + nums[i];// 维护单调递减性质：移除队尾所有小于等于当前得分的元素while (deque.Count > 0 && deque.Last.Value.score <= dp[i]) {deque.RemoveLast();}// 将当前位置的得分加入队列deque.AddLast((dp[i], i));}return dp[n - 1];}
}