单调栈单调队列学习笔记

目录：

1. 单调栈
   1.1 概念
   1.2 实现
   1.3 时间复杂度分析
   1.4 应用
2. 单调队列
   1.1 概念
   1.2 实现
   1.3 时间复杂度分析
   1.4 应用
3. 习题

1.单调栈

1.1 概念

单调栈为满足单调性的栈结构，栈内元素满足单调性。

1.2 实现

为满足单调性，在遍历到一个元素时，若此时加入后栈不满足单调性，则弹出栈顶。最后将该元素加入。
代码实现：

int stk[N],top;
int a[N];
for(int i=1;i<=n;i++)
{
    while(top&&a[stk[top]]<a[i]) top--;
    stk[++top]=i;
}

1.3 时间复杂度分析

由于只有一层循环，所以时间复杂度为 \(O(n)\)。

1.4 应用

我们发现，若我们在弹栈时使用一个数组记录该元素所对的值为 \(i\)，记该数组为 \(h[i]\)，则易发现，我们可以用单调栈维护数列中每个元素左右第一个比它大的元素位置。

2.单调队列

1.1 概念

单调队列为满足单调性的队列结构。

1.2 实现

我们维护队列，在每次加入元素的时候，不仅我们要判断加入后是否满足单调性，还要保证队首元素有没有超过队列长度限制。
所以我们要维护队首与队尾。

int hd=1,tl=0;
//k为规定长度
for(int i=1;i<=n;i++)
{
    while(hd<=tl&&q[hd]<i-k+1) hd++;
    while(hd<=tl&&a[q[tl]]>a[i]) tl--;
    q[++tl]=i;
}

1.3 时间复杂度分析

由于只有一层循环，所以时间复杂度为 \(O(n)\)。

1.4 应用

单调队列一般应用与求区间最小值。