单调队列和单调栈是两种神奇的数据结构。此处的单调是指不断维护在队列和栈中的元素，使得其始终满足一个性质，如 (a_i>a_{i-1})。可以用较高的效率和较短的代码来解决动态区间最大（小）类的问题。
单调队列
单调队列在维护的过程中，需要对队尾的元素进行维护，如果当前的元素与即将加入的元素不满足此单调性质，就将其弹出。
如果想维护一个区间，可以采用双向队列，在队首维护不满足区间的元素。
在这里，我会以 STL 中包括在 queue 头文件的 deque 来实现双向队列。单调队列维护序列动态区间一般模板如下：
for(/*遍历序列*/)
{
/*取得所要入队的元素*/
while(!que.empty()&& /*不满足这个单调性质*/)
que.pop_back(); //弹出。
que.push_back(); //将元素压入队列
while(/*如果不在此区间内*/)
que.pop_front(); //同样需要弹出。
}
取区间最大和最小的时间复杂度就为 (Theta(1))：
cout<<que.front();
熟练运用模板而不局限于模板。单调有许多变体，将单调队列与其它的算法和数据结构结合在一起，可以实现更强大的功能。
本题是一道典型的单调队列，需要在窗口（区间）滑动的过程中，维护一个单调递增和单调递减的序列。在队列中存储数字和其编号，分别用来维护“单调”和区间。套用上面的模板，就可以解决此问题。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int a[1000005],n,m,k,cnt=1;
struct node
{
int idx,val;
}now;
deque<node> q1;
deque<node> q2;
int main()
{
cin>>n>>k;
for(register int i=1;i<=n;i++)
cin>>a[i];
for(register int i=1;i<=n;i++)
{
now.idx=i;
now.val=a[i];
while(q2.empty()==0&&a[i]<=q2.back().val)
q2.pop_back();
q2.push_back(now);
while(i-k>=q2.front().idx)
q2.pop_front();
if(i>=k) //此处是因为本题的特殊性质，i<k 的话窗口放不下，在前 k 此不用输出。
cout<<q2.front().val<<" ";
}
cout<<endl;
for(register int i=1;i<=n;i++)
{
now.idx=i;
now.val=a[i];
while(q1.empty()==0&&a[i]>=q1.back().val)
q1.pop_back();
q1.push_back(now);
while(i-k>=q1.front().idx)
q1.pop_front();
if(i>=k)
cout<<q1.front().val<<" ";
}
return 0;
}
单调栈
其实单调栈和单调队列的思想是一致的，都是靠弹出元素来维护“单调”的性质。但是在实际操作中，单调队列比单调栈更常用，因为单调栈能解决的问题，一般单调队列也能解决；但单调队列能解决的问题，单调栈不一定能解决。
单调栈的模板：
for(/*遍历这个序列*/)
{
/*取得所要入栈的元素*/
while(st.empty()==0&& /*栈顶元素不满足单调性质*/)
{
st.pop() //栈顶元素出栈;
//更新结果;
}
que.push_back(); //将元素压入栈
}
感兴趣的可以尝试做做这道题，可以分别用单调队列和单调栈打两种代码。
小结
单调队列和单调栈是帮助我们优化算法的数据结构，很多的题中离不开它们的身影。熟练运用，熟练改编，更多用法需要自己去发现。