基本思想就是用一个set存下 各个值及其位置

然后，每次循环时确保set的begin() 和 end()-1处的值在window范围里边

取出最大，最小值，放进两个vector里边，按理说复杂度 O(nlogn)应该没有问题阿

#include<iostream>
#include<set>
#include<vector>
#include<iterator>
using namespace std;

//array是输入数组
int array[1000010];

//Elem记录值以及值的位置
class Elem
{
    public:
	int value;
	int pos;
	friend bool operator < (const Elem& e1, const Elem& e2)
	{
	    if(e1.value==e2.value)
		return e1.pos<e2.pos;
	    return e1.value<e2.value;
	}
};

//如果n<k,简单情形，直接打印
void Simplify(int N,int K)
{
    int imin=array[0];
    int imax=array[0];
    int i;
    for(i=1;i<N;i++){
	if(array[i]<imin)imin=array[i];
	if(array[i]>imax)imax=array[i];
    }
    cout<<imin<<endl
	<<imax<<endl;
    return ;
}
int main()
{
    set<Elem> data;
    set<Elem>::iterator it;
    int n,k; cin>>n>>k;
    Elem e;
    int i,j;
    for(i=0;i<n;i++)cin>>array[i];
    if(n<=k){
	Simplify(n,k);
	return 0;
    }
//先将前k个数，全部放进一个set里边
    for(i=0;i<k;i++)
    {
	e.value=array[i];
	e.pos=i;
	data.insert(e);
    }
//存储最大值，最小值
    vector<int> minV;
    vector<int> maxV;
    it=data.begin();
    minV.push_back(it->value);
    it=data.end();it--;
    maxV.push_back(it->value);

    j=0;
//后边的数，依次放进set,
    for(i=k;i<n;i++)
    {
	int startPos=i-k+1;
	e.value=array[i];
	e.pos=i;
//去掉window以外的数
	while(1)
	{
	    it=data.begin();
	    if(it->pos < startPos)
		data.erase(it);
	    else break;
	}
	while(1)
	{
	    it=data.end();
	    it--;
	    if(it->pos < startPos)
		data.erase(it);
	    else break;
	}
	data.insert(e);

	it=data.begin();
	minV.push_back(it->value);
	it=data.end();it--;
	maxV.push_back(it->value);
    }
//输出结果
    for(i=0;i<(n-k);i++)
	cout<<minV[i]<<" ";
    cout<<minV[n-k]<<endl;

    for(i=0;i<(n-k);i++)
	cout<<maxV[i]<<" ";
    cout<<maxV[n-k]<<endl;
    return 0;
}