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 <= 10^5
-10^4 <= nums[i] <= 10^4

思路

很容易想到的就是动态规划，设表示为跳到位置的最大分数，状态转移方程为#card=math&code=dp%5Bi%5D%20%3D%20nums%5Bi%5D%20%2B%20Math.max%28dp%5Bi%20-%201%5D%2C%20dp%5Bi%20-%202%5D%2C%20…%2C%20dp%5Bi%20-%20k%5D%29&id=EoIiJ)，最后返回就好了。但是，因为和都是次方量级，必然超时。

由于取决于前面k个数的最大值，那么可以借助的思路，使用优先队列或者单调队列来优化。这里使用单调队列优化，单调队列中是单调递减的值的下标。

这里和不同的是，要先更新，而更新之前要先掉队头不在区间内的数，因此循环内的逻辑顺序和不太一样，要注意一下。

代码

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        k = Math.min(k, n - 1);
        int[] dp = new int[n];
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offerLast(0);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            while (i - deque.peekFirst() > k) {
                deque.pollFirst();
            }
            dp[i] = nums[i] + dp[deque.peekFirst()];
            while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        return dp[n - 1];
    }
}