写法
首先要有一个双端队列：
struct My_dequeue{
int hh=1,tt=0,q[N];
void clear(){hh=1;tt=0;}
void push_front(int k){q[--hh]=k;}
void push_back(int k){q[++tt]=k;}
void pop_front(){hh++;}
void pop_back(){tt--;}
int front(){return q[hh];}
int back(){return q[tt];}
int head(){return hh;}
int tail(){return tt;}
bool empty(){return hh>tt;}
}q;
以下给出单调队列的标准写法。
int calc(int i){//返回下标对应的值
return inp[i];
}
void insert(int x){//传入下标
while(!q.empty()&&calc(q.back())<=calc(x)) q.pop_back();//维护最大值
q.push_back(x);//存入下标
}
int query(int x){
while(q.front()<=x-k) q.pop_front();//弹出不符合条件的下标
return calc(q.front());//返回值
}
q.clear();
for(int i=1;i<=n;i++){
insert(i);
ans[i]=query(i);
}
作用
维护左右端点单调的若干定长连续区间的 RMQ。
可以用于优化 DP 。要求当前状态的所有值可以从上一个状态的某个连续的段的值得到，将要对这个连续的段进行 RMQ 操作，且相邻状态的段的左右区间满足非降的关系。
具体的说，要求 DP 的状态转移方程满足以下形式（ \(b\) 为任意与\(k\)无关的式子，\(x,y\) 为任意与$j $无关的式子）：
\[f(i,j)=\max\{f(i-1,k)\}+b,k\in[j-x,j+y] \]\[f(i)=max\{f(k)\}+b,k\in[i-x,i-y],x>0,y>0 \]那么，就可以通过单调队列优化其时间复杂度。
具体的说，我们可以用单调队列维护上一层的 DP 数组的区间最值。由于每一层内求最值的区间长度固定，就可以仿照上面的写法将其构造成一个单调队列，计算新状态时就可以以均摊 \(O(1)\) 的时间复杂度维护最值信息，这样总时间复杂度就可以少一个 \(n\)。是一个优秀的优化。
单调队列优化通常配合滚动数组一起适用，可以让时空均少一个 \(n\)。
例如：
\[f(i)=max\{f(k)\}+a[i],k\in[i-R,i-L] \]那么代码是这样的：
int calc(int i){//返回下标对应的值
return f[i];
}
void insert(int x){//传入下标
while(!q.empty()&&calc(q.back())<=calc(x)) q.pop_back();//维护最大值
q.push_back(x);//存入下标
}
int query(int x){
while(q.front()<=x-R-1) q.pop_front();//弹出不符合条件的下标
return calc(q.front());//返回值
}
q.clear();
for(int i=L;i<=n;i++){
insert(i-L);
f[i]=query(i)+a[i];
if(i+R>n) ans=max(ans,f[i]);
}