1696. 跳跃游戏 VI
给你一个下标从 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
解题思路
方法一： 动态规划 + 优先队列
保存以i结尾的最大值, 然后保存当前位置的前k个位置相应的最大值, 然后采用优先队列, 找到最大值。在滑动窗口滑动之后, 首先要判断最大值的位置到当前位置是否可以, 如果不可达, 则移除堆顶元素。
public int maxResult(int[] nums, int k) {
PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> Integer.compare(o2[1], o1[1]));
queue.add(new int[]{0, nums[0]});
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
// 将堆顶的不符合要求的最大元素删除
// 堆中有效元素 应该为f[i-k] ... f[i-1]的元素
while (!queue.isEmpty() && i - queue.peek()[0] > k) {
queue.poll();
}
res = queue.peek()[1] + nums[i];
queue.add(new int[]{i, res});
}
return res;
}
方法二： 动态规划 + 单调队列优化
类似于滑动窗口, 在i之前的K大小的滑动窗口中, 选择一个值最大的。
类似于Hard | LeetCode 239 | 剑指 Offer 59 - I. 滑动窗口的最大值 | 单调队列 使用一个单调递减队列, 可以在一个滑动窗口当中, 找到一个最大的元素。
public int maxResult(int[] nums, int k) {
Deque<int[]> slideWindows = new ArrayDeque<>();
slideWindows.push(new int[]{0, nums[0]});
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
while (i - slideWindows.getLast()[0] > k) {
slideWindows.removeLast();
}
res = slideWindows.getLast()[1] + nums[i];
while (!slideWindows.isEmpty() && slideWindows.peek()[1] < res) {
slideWindows.pop();
}
slideWindows.push(new int[]{i, res});
}
return res;
}