简介
单调栈和单调队列都是思维难度比较大的数据结构，但只要想明白了就会觉得很简单。
要理解单调队列，首先得明白“单调”是指它存储的内容单调，而不是指它简单。
实现
模板题（AcWing.154）
题目描述
给定一个大小为 \(n≤10^6\) 的数组。
有一个大小为 \(k\) 的滑动窗口，它从数组的最左边移动到最右边。
请输出滑动窗口位于每个位置时，窗口中的最大值和最小值。
样例
in:
8 3
1 3 -1 -3 5 3 6 7
out:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
单调队列实现
思路
先看题目给的表：
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
首先考虑用暴力怎么做，一定要先思考一下暴力！不然很难理解单调队列！（优化后的暴力）
先计算最小值。
这些数可以看做是一个队列，队头是 \(l\) ，队尾是 \(r\) ，每次滑动窗口，都是 \(l+1\) ， \(-1\) 。
显然很多窗口中都有一些我们肯定不需要的数。
考虑优化。
可以发现，在如果队列中存在 \(x<y\) 且 \(a_x≥a_y\) ，那么 \(a_x\) 就没用了。因为只要 \(a_y\) 在队列中，\(a_x\) 就永远不可能输出，而且 \(a_y\) 在 \(a_x\) 后面，会比 \(a_x\) 的出栈时间晚（通俗点讲就是 \(a_y\) 比 \(a_x\) 活得久）。
这样一来，这个序列就成了单调递减的了，每次查询输出右端点 \(a_r\) 就行了。
计算最大值同理。
用单调队列维护后会得到单调递增的一个队列，每次查询也是输出右端点 \(a_r\) 。
代码
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return (f==1)?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),k=read(),l,r=-1,a[N],q[N];
int main()
{
for(ll i=0;i<n;i++) a[i]=read();
for(ll i=0;i<n;i++)
{
if(l<=r&&i-k+1>q[l]) l++;
while(l<=r&&a[i]<=a[q[r]]) r--;
q[++r]=i;
if(i>=k-1) write(a[q[l]]),putchar(' ');
}
putchar('\n');l=0,r=-1;
for(ll i=0;i<n;i++)
{
if(l<=r&&i-k+1>q[l]) l++;
while(l<=r&&a[i]>=a[q[r]]) r--;
q[++r]=i;
if(i>=k-1) write(a[q[l]]),putchar(' ');
}
return 0;
}