滑动窗口应用

简单记录下滑动窗口的应用场景。

计算窗口内最大/最小值

核心思想是使用deque即双向队列。如1696. 跳跃游戏 VI，核心思想是dp的延伸，但是使用到滑动窗口维护前k个数内的最大值，那么我们使用一个deque，从前往后降序排列，取的时候从前面取出。

for (int i = 1; i < n;i++) {
    while (q.size() && i-q.front()>k) q.pop_front(); // 每次从前面pop不在范围内的
    f[i] = f[q.front()] + nums[i]; // 肯定是最大值所以直接计算跳到i位置的最大值
    while (q.size()  && f[i] > f[q.back()])q.pop_back(); // 比i小的值肯定没用了，去除同时保证队内的顺序
    q.push_back(i);
}