---
# System prepended metadata

title: 1696. Jump Game VI
tags: [Leetcode, Dynamic Programming, Medium, Deque]

---

# 1696. Jump Game VI
###### tags: `Leetcode` `Medium` `Deque` `Dynamic Programming`
Link: https://leetcode.com/problems/jump-game-vi/
## 思路
可以想到的是 我们可以基本型II dp
用dp算到每个位置的最大score
```score[i] = nums[i]+Math.max(score[i-1],score[i-2], ..., score[i-k-1])```
但是这样的时间复杂度会是$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
```java=
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;
    }
}
```