单调队列

7 6 8 12 9 10 3
求最大值

i=0*i*=0，队列初始化0，队列为{0}
i=1*i*=1，因为7>07>0，所以7入队，0出队（要维护这个队列单调递减），队列为{7}
i=2*i*=2，因为6<76<7，所以6入队，队列为{7，6}
i=3*i*=3，因为8>68>6，所以6出队，8>78>7，所以7出队，8入队，队列为{8}
i=4*i*=4，因为12>812>8，所以8出队，12入队，队列为{12}
i=5*i*=5，因为9<129<12，所以9入队，队列为{12，9}
i=6*i*=6，因为10>910>9，所以9出队，10<1210<12，所以10入队，队列为{12，10}
i=7*i*=7，因为3<103<10，所以3入队，队列为{12，10，3}，但是，因为12的位置为4，不在(i-3,i](*i*−3,*i*]，这个范围内，所以出队，队列为{10，3}

这时就有人奇怪了，队列里剩下的不是最大值呀

其实不难发现，每个队列的队头就是当前的最大值，所以只要每次更新完队列后让更新前的最大值与更新后的最大值比较就行

最小值同理

#include<bits/stdc++.h>

const int N=200010;
using namespace std;

int n,m,l,r;
int a[N],q[N];

int main()
{
    scanf("%d",&n);
	scanf("%d",&m);
    
    for(int i =1;i<=n;++i)
        a[i] = in();
    cout<<'0'<<endl;
    l=1,r=1;//初始化
    q[1] =1;
    for(int i=2;i<=n;++i)
    {
        while(l<=r && q[l]+m<i) ++l;
        printf("%d\n",a[q[l]]);
        
        while(l<=r && a[i]<a[q[r]]) --r;
        
        q[++r]=i;//储存位置
    }
    system("pause");
    return 0;
}

deque<int> q;
q.push_back(0),b[0] = 0;;
   for(int i =1;i<=n;++i)
   {
       //前缀和 
   	b[i] = b[i-1] + a[i];
   	 
   	//while(!q.empty()&&q.front()+m<i)   m = n
	//	q.pop_front();   
	
   	//求区间[q.front,i]连续和，并更新最大值。
	ans = max(ans,b[i]-b[q.front()]);
	
	//维护队列单调性 
       while(!q.empty()&&b[i]<=b[q.back()])  
		q.pop_back();
       //当前元素入队 
	q.push_back(i);
}