题目描述
给你一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下表所示：
窗口位置 最小值 最大值
[ 1 3 -1 ] -3 5 3 6 7 -1 3
1 [ 3 -1 -3 ] 5 3 6 7 -3 3
1 3 [ -1 -3 5 ] 3 6 7 -3 5
1 3 -1 [ -3 5 3 ] 6 7 -3 5
1 3 -1 -3 [ 5 3 6 ] 7 3 6
1 3 -1 -3 5 [ 3 6 7 ] 3 7
你的任务是找出窗体在各个位置时的最大值和最小值。
输入
第一行：两个整数N和K
第二行：N个整数，表示数组的N个元素（<=2*10^9）。
输出
第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开。
第一行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
提示
对于20%的数据，K<=N<=1000.
对于50%的数据，K<=N<=100000.
对于100%的数据，K<=N<=1000000.
思路：
这是一个单调队列模板题。
维护一个长度为k的单调队列，每次用队首来的出最大和最小值，新加入的数就放在队尾。
如果队首的距离大于k，则head++，即队首出队。若新来的数值比队尾更优，则tail--，即队尾出队。
代码
#include <bits/stdc++.h>
using namespace std;
struct node{
int u;//值
int v;//id
}q[10000001];
int a[10000001];//定义权值的输入
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int head=1,tail=0,i;//队首和队尾
//求最小值
for(i=1;i<k;i++)//对第1~k-1的数进行操作
{
while(a[i]<q[tail].u&&tail>0)
tail--;//将不符合规定的队尾删掉，即tail<=0或队尾的数值比该次遍历的数值小
q[++tail].u=a[i];//将该数值加入队尾
q[tail].v=i;//记录id值
}
for(i=k;i<=n;i++)//对k~n的数操作
{
while(a[i]<q[tail].u&&tail>=head)
tail--;//将将不符合规定的队尾删掉，即tail<=0或队尾的数值比该次遍历的数值小
q[++tail].u=a[i];//将该数值加入队尾
q[tail].v=i;//记录id值
while(q[head].v+k<=i&&head<=tail)//将将不符合规定的队首删掉，即队首比队尾大或队首的id加上看k达不到i
head++;
cout<<q[head].u<<" ";//输出
}
cout<<'\n';
head=1,tail=0,i;//求最大值，重新初始化，同上
for(i=1;i<k;i++)
{
while(a[i]>q[tail].u&&tail>0)
tail--;
q[++tail].u=a[i];
q[tail].v=i;
}
for(i=k;i<=n;i++)
{
while(a[i]>q[tail].u&&head<=tail)
tail--;
q[++tail].u=a[i];
q[tail].v=i;
while(q[head].v+k<=i&&head<=tail)
head++;
cout<<q[head].u<<" ";
}
cout<<'\n';
}
京公网安备 11010502036488号