时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K 其他语言 65536K
64bit IO Format:%lld
给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下图：
你的任务是找出窗体在各个位置时的最大值和最小值。
输入描述:
第1行：两个整数N和K； 第2行：N个整数，表示数组的N个元素(≤2×109)；
输出描述:
第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；
第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。
示例1
输入
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≤105
对于100%的数据，K≤N≤106
题解：
老题了。。
（想起来我当年逝去的OI梦 ）
赶紧从洛谷找到以前的代码
就是单调队列的模板题
手写就完事了
构造一个单调队列，
我们来模拟下过程：
（以求最小为例）
head指向头，tail指向尾
a[]是我们一开始存放的数
mi存放的是最小值的坐标（即 i ）
i是指向数组a当前位置
m=3
例如 1 3 -1
坐标 1 2 3
1和3顺利存入mi中（存的是坐标）mi={1,2}；
读入-1时与前面的进行比较，-1<3然后tail–，-1<1,tail–,直到整个区间都比完（也就是tail大于head时），或者是出现比-1还小的数x，tail就在x的位置停下来。然后将-1的坐标存入到mi[++tail]中,说明从tail之后没有比-1还小的了.
m=3
例如1 2 4 5 4
如果读入的数没有比之前小的，就依次读入mi中，mi=[1,2,3],head=1;当i=4时,就超出m的范围时（mi[head]+m<=i），就将区间向后移动（head++，头向后移动，整个区间也跟着移动），随着输出（将多的输出来）
然后一直循环就可以了。
head指的是mi，mi反应的是当前最小值在a中的坐标
也可以写两个数组来一个表示单调队列，一个表示对应的在原列表里的序号，我这就用了一个。
（话说线段树也可以做）
讲的我自己也有点乱，明白但是讲不大出来，结合者代码看吧
#include<bits/stdc++.h>
#define for(n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn=1e6+3;
int a[maxn];
int ma[maxn];
int mi[maxn];
void min(int n,int m)
{
int head=1;
int tail=0;
for(n)
{
while(head<=tail&&mi[head]+m<=i)
head++;//向后移动head
while(head<=tail&&a[i]<a[mi[tail]])
tail--;//向前移动tail
tail++;
mi[tail]=i;
if(i>=m)cout<<a[mi[head]]<<" ";//如果元素超出就输出当前区域最小
}
}
void max(int n,int m)
{
int head=1;
int tail=0;
for(n)
{
while(head<=tail&&ma[head]+m<=i)head++;
while(head<=tail&&a[i]>a[ma[tail]])tail--;
tail++;
ma[tail]=i;
if(i>=m)cout<<a[ma[head]]<<" ";
}
}
int main()
{
int n,m;
cin>>n>>m;
for(n)cin>>a[i];
min(n,m);
cout<<endl;
max(n,m);
return 0;
}
京公网安备 11010502036488号