题目描述
有一个长为 nn 的序列 aa，以及一个大小为 kk 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7], and k = 3k=3。
输入格式
输入一共有两行，第一行有两个正整数 n,kn,k。 第二行 nn 个整数，表示序列 aa
输出格式
输出共两行，第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值
输入输出样例
输入 #1复制
代码语言：javascript复制8 3
1 3 -1 -3 5 3 6 7输出 #1复制
代码语言：javascript复制-1 -3 -3 -3 3 3
3 3 5 5 6 7说明/提示
【数据范围】 对于 50P% 的数据，1 le n le 10^51≤n≤105； 对于 1000% 的数据，1le k le n le 10^61≤k≤n≤106，a_i in [-2^{31},2^{31})ai∈[−231,231)。
单调队列板子题：
我们用q来表示单调队列，p来表示其所对应的在原列表里的序号。
- 由于此时队中没有一个元素，我们直接令1进队。此时，q={1},p={1}。
- 现在3面临着抉择。下面基于这样一个思想:假如把3放进去，如果后面2个数都比它大，那么3在其有生之年就有可能成为最小的。此时，q={1,3},p={1,2}
- 下面出现了-1。队尾元素3比-1大，那么意味着只要-1进队，那么3在其有生之年必定成为不了最小值，原因很明显:因为当下面3被框起来，那么-1也一定被框起来，所以3永远不能当最小值。所以，3从队尾出队。同理，1从队尾出队。最后-1进队，此时q={-1},p={3}
- 出现-3，同上面分析，-1>-3，-1从队尾出队,-3从队尾进队。q={-3}，p={4}。
- 出现5，因为5>-3，同第二条分析，5在有生之年还是有希望的，所以5进队。此时，q={-3,5},p={4,5}
- 出现3。3先与队尾的5比较，3<5，按照第3条的分析，5从队尾出队。3再与-3比较，同第二条分析，3进队。此时，q={-3,3},p={4,6}
- 出现6。6与3比较，因为3<6，所以3不必出队。由于3以前元素都＜3，所以不必再比较，6进队。因为-3此时已经在滑动窗口之外，所以-3从队首出队。此时，q={3,6},p={6,7}
- 出现7。队尾元素6小于7，7进队。此时，q={3,6,7},p={6,7,8}。
那么，我们对单调队列的基本操作已经分析完毕。因为单调队列中元素大小单调递*(增/减/自定义比较)，因此，队首元素必定是最值。按题意输出即可。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3) (x<<1) (ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res =sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x] =val;x =lb(x);}}//第x个加上val
ll k,q[1000005],p[1000005],a[1000005];
vector<ll>ans1,ans2;
inline void minn()
{
int head=1,tail=0;
for(int i=1;i<=n;i )
{
while(head<=tail&&q[tail]>=a[i])tail--;
q[ tail]=a[i];
p[tail]=i;
while(p[head]<=i-k)head ;
if(i>=k)ans1.push_back(q[head]);
}
}
inline void maxx()
{
int head=1,tail=0;
for(int i=1;i<=n;i )
{
while(head<=tail&&q[tail]<=a[i])tail--;
q[ tail]=a[i];
p[tail]=i;
while(p[head]<=i-k)head ;
if(i>=k)ans2.push_back(q[head]);
}
}
inline void printt(vector<ll>&ans)
{
for(int i=0;i<ans.size();i )
{
i==ans.size()-1?cout<<ans[i]:cout<<ans[i]<<" ";
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i )cin>>a[i];
minn();
printt(ans1);
puts("");
maxx();
printt(ans2);
return 0;
}
