单调队列两种实现方法

P1886 滑动窗口 /【模板】单调队列

思路:

用一个数组q[N]来演示队列用一个变量h来指明队头下标,用t来指明队尾下标数组q[N]存储a[N]的元素下标根据条件调整队头和队尾元素出队

#includeusing namespace std;#define N 10000005int a[N],q[N];int n,k;int main(){cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];//求最小值 int h=1,t=0;for(int i=1;i<=n;i++){//窗口大小为k,i为窗口右端点,i-k+1为窗口左端点下标//q[h]是此时队列中队头元素的下标,如果此时队头的下标超出窗口左端点,则出队 while(t>=h && i-k+1>q[h])h++;//待入队元素a[i],若队尾元素小于a[i]则出队 while(t>=h && a[i]=k)cout<=h && i-k+1>q[h])h++;while(t>=h && a[i]>a[q[t]])t--;q[++t]=i;if(i>=k)cout< deque双端队列

原理和上面类似