[单调队列] 洛谷P1886 滑动窗口_有一个长度为n的数列,一个长度为k的窗口,输出窗口位于每个位置下的下的最大值

题目链接
dalao题解
题目给一个长度为n的序列,然后给一个值k,要求出长度为k的窗口在数列滑动过程中的最大值和最小值;
图示如下:
比如给一个长度为n=8的序列为:
1 3 -1 -3 5 3 6 7
窗口长度是k=3
那么窗口滑动中的
最小值就是 -1 -3 -3 -3 3 3
最大值就是 3 3 5 5 6 7

这题大概是一个单调队列的模板题…
单调队列就是一个从队首到队尾满足单调性的队列,比如单调递增或者单调递减,如果要加入一个新的元素,就加入队尾,如果加入的元素破坏了单调队列的单调性,就执行pop_back操作,直到满足单调性位置;

这题我们需要维护两个单调队列,一个是最大值队列,一个是最小值队列;以维护最大值队列为例;
在每次滑动前,从队首开始遍历整个序列,如果有某个元素已经不在窗口内了(过时了)就执行pop_front;
然后再从队尾开始遍历整个序列,如果队尾的元素比即将新加进来的元素还小,那么这个队尾元素就始终不可能成为以后窗口中的最大值了(因为他会比新加入的元素更早的过时),所以可以执行pop_back;
如是,我们的队首元素就始终是当前窗口中的最大值了;

具体实现我是用的dequeue,因为涉及到pop_front和pop_back操作,用dequeue比较方便;

整体代码如下:

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxx=1e6+6;
int n,k;
int a[maxx];
deque<int> p,q;
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
            while(!p.empty() && (p.front()+k<=i) ) p.pop_front();
            while(!p.empty() && (a[p.back()]>a[i]) ) p.pop_back();
            p.push_back(i);
            if(i>=k) printf("%d ",a[p.front()]);
        }
    cerr<<endl;
    for(int i=1;i<=n;i++){
            while(!q.empty() && (q.front()+k<=i) ) q.pop_front();
            while(!q.empty() && (a[q.back()]<a[i]) ) q.pop_back();
            q.push_back(i);
            if(i>=k) printf("%d ",a[q.front()]);
        }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

错点:
1.i>=k的时候就可以直接输出值了,不用新开数组来存答案;
2.洛谷oj貌似对输出的答案的空格不敏感,所以直接放心的在答案后面输出空格就好;
3.这题好像用cin cout会挂… 老老实实用标准读写了