时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K 其他语言 65536K
64bit IO Format:%lld

题目描述

给一个长度为N的数组,一个长为K的滑动窗体从最左端移至最右端,你只能看到窗口中的K个数,每次窗体向右移动一位,如下图:

在这里插入图片描述

你的任务是找出窗体在各个位置时的最大值和最小值。

输入描述:

第1行:两个整数N和K; 第2行:N个整数,表示数组的N个元素(≤2×10^9^);

输出描述:

第一行为滑动窗口从左向右移动到每个位置时的最小值,每个数之间用一个空格分开;
第二行为滑动窗口从左向右移动到每个位置时的最大值,每个数之间用一个空格分开。

示例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≤10^5^
对于100%的数据,K≤N≤10^6^
题解:
老题了。。
想起来我当年逝去的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;
}