题解 | #滑动窗口#

思路

应该是单调队列的板子题吧。我用的是双向队列deque（可能会比较慢）。
原理很简单，对于需要输出大的那个数的队列，比较最后的元素是否比新加入的数小，
是的话就弹出最后的元素，重复此操作，最终得到一个单调递增的队列。
如果队首的元素滑出窗口了，那么直接pop掉，对另外一个队列也是同理。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
deque<int>big,sml;
int n,k,num[maxn];

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>num[i];
    for(int i=1;i<=n;i++){
        while(!big.empty()&&num[big.front()]>num[i]) big.pop_front();
        big.push_front(i);
        if(big.back()<=i-k) big.pop_back();
        if(i>=k) cout<<num[big.back()]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        while(!sml.empty()&&num[sml.front()]<num[i]) sml.pop_front();
        sml.push_front(i);
        if(sml.back()<=i-k) sml.pop_back();
        if(i>=k) cout<<num[sml.back()]<<" ";
    }
    return 0;
}