# 1696. Jump Game VI
###### tags: `Leetcode` `Medium` `Deque` `Dynamic Programming`
Link: https://leetcode.com/problems/jump-game-vi/
## 思路
可以想到的是 我们可以基本型II dp
用dp算到每个位置的最大score

但是这样的时间复杂度会是$O(Nk)$

我们可以发现```Math.max(score[i-1],score[i-2], ..., score[i-k-1])```这一部分我们可以用Sliding Window Maximum解决
我们关注一个长度为k的滑动窗口，里面的最大值就用来更新窗口后的第一个元素的dp值。sliding window maximum的标准解法是用deque，维护一个单调递减的队列。如果有新元素比队尾元素更大，那么它就更有竞争力（更新、更大）被用来更新后面的dp值，故队尾元素就可以舍弃而加入新元素。此外，如果队首元素脱离了这个滑动窗口的范围，也就可以将其舍弃。在每一个回合，deque里面的最大元素就是队首元素。

Sliding Window Maximum模版:

Deque<int[]> q = new ArrayDeque<>();
for(int i=0; i<nums.length; i++){
超出范围的部分先pollFirst()弄掉
计算当前的max (不能调换位置)
把queue里面小于当前值的部分都pollLast()弄掉 (因为他们又老又旧，之后不会用到)
q.add() 加入当前值
}

## Code

class Solution {
public int maxResult(int[] nums, int k) {
Deque<int[]> q = new ArrayDeque<>();
int ans = 0;
int max = 0;
for(int i=0; i<nums.length; i++){
while(!q.isEmpty() && i-q.getFirst()[0]>k){
q.pollFirst();
}
if(!q.isEmpty()){
max = q.getFirst()[1];
}
while(!q.isEmpty() && q.getLast()[1]<max+nums[i]){
q.pollLast();
}
q.add(new int[]{i, max+nums[i]});
if(i==nums.length-1) return max+nums[i];
}
return 0;
}
}