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

计算窗口内最大/最小值

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

1
2
3
4
5
6
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);
}