前言
最近感觉遇到了好多单调队列和单调栈的问题，但是因为以前没学好，所以遇见了就一脸懵逼，然后绝对下决心来学一下。。感觉遇到啥都不会，这可咋办呐。。补不完的漏洞。
单调队列(Monotone queue)
单调队列，即单调递减或单调递增的队列。使用频率不高，但在有些程序中会有非同寻常的作用。
理解
顾名思义，他就是一个单调的队列，那么我们可以规定他是单调递增的还是单调递减的，他和普通的队列有点区别，队列一般是尾进头出，而单调队列要实现的话要确保头和尾都可以出，尾可以进。如果要用STL库的话可以用里面的双端队列。 跟普通队列相比他的进队需要确保一个条件就是要不破坏原有序列的单调性，好比我们有一个单调递增的单调队列，也就是从队首到队尾是单调递增的，那么有一段序列是 $[2,3,1,5,8,7,4,2]$ ，我们从左到右依次入队。
| 队列中元素 | 关于元素进出的备注 |
|---|---|
| 2 | 2入队 |
| 2，3 | 3比2大，可以满足递增性质，入队 |
| 1 | 因为1比2，3都小，要满足递增性质，先把2，3出队，再将1入队 |
| 1，5 | 5比1大，可以满足递增性质，入队 |
| 1，5，8 | 8比5大，可以满足递增性质，入队 |
| 1，5，7 | 7小于8，大于5，要满足递增性质，我们把8出队，然后将7入队 |
| 1，4 | 4小于5、7，但是大于1，因此7，5依次出队，4入队 |
| 1，2 | 2小于4，大于1，因此4出队，2入队 |
根据上述例子不难看出，我们要入队的时候首先要确保队尾元素要比想要入队的元素小，然后才能入队，否则的话就一直循环让尾部元素出队，直到能够满足单调性为止。
单调队列的应用
- 求区间的最值问题。下面写的两个例题都是这个用处。
- 优化dp，我现在能接触到的就是一个用单调队列优化多重背包的一个题，但是那个题我学了这个东西之后还是不理解为什么可以那么做。例题如下：宝物筛选
单调队列的一些例题
A. Sliding Window
题意
给出一个含有 $n$ 个整数的序列 $a$ ，给出滑动窗口长度 $k$ ，窗口从序列最左端滑动到序列最右端，问滑动过程中每个时刻窗口中最大值和最小值是多少。
思路
一道很经典的单调队列的模板题，用于解决定长区间的最大最小值。我们可以维护两个单调队列，一个是单调递增的，一个是单调递减的。因为两种情况类似，我们考虑一下求窗口中最大值的方案。
求最大值我们用的是单调递减的序列，这样就能够保证每次队首的就是答案，但是，这是为什么呢？我们来考虑一下，因为这是一个单调递减的序列，那么我们每次序列元素入队的时候，我们就去看当前队尾的元素是不是要比他大，如果比他还小，那么我们就直接将队尾元素出队，因为这时候要入队的元素（已经被窗口覆盖了）已经比他大了，那么在接下来的窗口中，肯定就没他什么事了，因为它一定不是最大的，那么如果一直将队尾元素出队到加入入队元素后还继续能保持队列的单调性了，但是这个元素还不是在队首，这就说明，队首的元素还是要比他大的（单调性易得）。
所以这时候队首元素就是这个窗口中最大的了吗？也还不能确定，因为我们还不能确保这个队首元素就在窗口中，因此我们需要看看这个元素的位置和当前入队元素的位置之差是不是要比窗口长度大了，如果大于窗口长度，那么就说明队首元素已经不在窗口了，我们就将队首元素出队，最后输出队首元素就能确保它既在窗口中，又是窗口中所有元素的最大值了！
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn=1000005;
int n,k;
int head,tail,a[maxn];
struct node
{
int pos,value;
}q[maxn];
void getmax()
{
head=tail=0;
for(int i=1;i<=n;i++)
{
while(head!=tail&&i-q[head].pos>=k) head++;
while(head!=tail&&a[i]<=q[tail-1].value) tail--;
q[tail].value=a[i],q[tail++].pos=i;
if(i>=k) printf("%d ",q[head].value);
}
putchar('\n');
for(int i=1;i<=n;i++) q[i].value=q[i].pos=0;
}
void getmin()
{
head=tail=0;
for(int i=1;i<=n;i++)
{
while(head!=tail&&i-q[head].pos>=k) head++;
while(head!=tail&&a[i]>=q[tail-1].value) tail--;
q[tail].value=a[i],q[tail++].pos=i;
if(i>=k) printf("%d ",q[head].value);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
getmax();
getmin();
return 0;
}
B. Max Sum of Max-K-sub-sequence
题意
给定长度为 $n$ 的整数循环序列 $a$ ，也就是$a[1],a[2],\cdots,a[n],a[1]\cdots$ 这样的序列，问最大连续长度为 $k$ 的连续子区间的序列和最大为多少，并且输出这个区间的左右坐标。
思路
我们把这道题转换一下，我们先处理好前缀和，好比我们要求 $a[1],a[2],a[3]$ 的序列和，那么也就是 $sum[3]-sum[0]$ ，因此我们在求这个题的时候就可以循环遍历 $1\sim{n-k+1}$ ，求长度为 $k$ 的定长区间中前缀和数组的最小值即可。但是我们要注意前缀和数组要处理到 $n-k+1$ 。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int inf=1000000;
const int maxn=200005;
int t;
int n,k,a[maxn],sum[maxn];
int head,tail;
struct node
{
int pos,value;
}q[maxn];
int ans,l,r;
int main()
{
// freopen("test.in","r",stdin);
scanf("%d",&t);
while(t--)
{
l=r=0;
head=tail=0;
ans=-inf;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=n+1;i<=n+k-1;i++)
{
sum[i]=sum[i-1]+a[i-n];
}
for(int i=1;i<=n+k-1;i++)
{
while(head!=tail&&i-q[head].pos>k) head++;
while(head!=tail&&sum[i-1]<=q[tail-1].value) tail--;
q[tail].pos=i-1,q[tail++].value=sum[i-1];
// if(i!=q[head].pos)
// {
int p=sum[i]-q[head].value;
if(p>ans)
{
ans=p;
int k=q[head].pos+1;
k>n?l=k%n:l=k;
i>n?r=i%n:r=i;
}
// }
}
printf("%d %d %d\n",ans,l,r);
for(int i=1;i<=n+k-1;i++) q[i].pos=q[i].value=-inf;
}
return 0;
}
单调栈(Monotone stack)
单调增或单调减的栈，跟单调队列差不多，但是只用到它的一端。
理解
单调栈也是在普通栈的基础上加了单调性，一般是用从栈底到栈顶的单调性来命名，好比从栈底到栈顶是单调递增的，那么他就是单调增的栈。跟单调队列一样，他的入栈规则也是要不破坏单调性，因此一个单调递增的栈如果有元素要入栈，如果他比栈顶的元素还要大，就可以直接入栈，如果他比栈顶的元素小，那么就要将栈顶的元素一直出栈到比要入栈元素小为止。如果序列为 $[2,3,1,5,4,7]$，要加入单调递增栈中，过程如下。PS：注意从左到右对应栈底到栈顶。
| 栈中的元素 | 关于元素进出的备注 |
|---|---|
| 2 | 元素2压入栈中 |
| 2，3 | 3大于2，压入栈中 |
| 1 | 1小于3、2，因此全部弹出将1入栈 |
| 1，5 | 5大于1，压入栈中 |
| 1，4 | 4比5小，比1大，弹出5，压入4 |
| 1，4，7 | 7大于4，压入栈中 |
根据上述描述不难看出，其实单调栈就是单调队列的半部分，他能完成的任务理论上单调队列都能够完成，但是有些时候不需要麻烦的去维护单调队列只需要维护单调栈即可完成。
单调栈的应用
- 确定一个元素的左边区间第一个比它大的元素，第一个比它小的元素
- 确定右边区间第一个比他大or比他小的元素（根据单调性来看）
- 确定这个元素是否是一定区间内的最值，或者确定以他为最值的区间长度
单调栈的一些例题
A. 单调栈模板
题意
给出含有 $n$ 个整数的序列 $a$ ，定义 $f(i)$ 为第 $i$ 个元素后第一个大于 $a_i$ 的下标，求 $f(1)\cdots f(n)$
思路
直接就是模板，对应了上述应用里的第二个。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn=3000005;
int n,a[maxn];
int stack[maxn];
int top,ans[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
a[0]=1e9+5;
for(int i=1;i<=n;i++)
{
while(top>=0&&a[i]>a[stack[top]])
{
ans[stack[top]] = i;
top--;
}
stack[++top]=i;
}
while(top)
{
ans[stack[top]]=0;
top--;
}
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
return 0;
}
B. 发射站
题意
某地有 $N$ 个能量发射站排成一行，每个发射站 $i$ 都有不相同的高度 $H_i$，并能向两边（两端的发射站只能向一边）同时发射能量值为 $V_i$ 的能量，发出的能量只被两边最近的且比它高的发射站接收。计算出接受能量最多的发射站接受的能量为多少。
思路
维护一个单调递减栈，一个元素新加进来如果是大于栈顶元素的话，那么栈顶元素出栈，并给入栈元素加上能量值。如果不大于栈顶元素的话，就将栈顶元素加上发射能量，然后将元素入栈。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn=1000005;
int n,h[maxn],v[maxn];
int stack[maxn],top,ans;
int f[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&h[i],&v[i]);
}
for(int i=1;i<=n;i++)
{
while(top>=0&&h[i]>h[stack[top]])
{
f[i]+=v[stack[top]];
top--;
}
f[stack[top]]+=v[i];
stack[++top]=i;
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}
C. 音乐会的等待
题意
给出一段序列 $a$ 代表 $n$ 个人，在一个区间 $[l,r]$ 如果区间内没有大于 $min(a[i],a[r])$ 的那么两个人可以相互看到。问这个序列中有多少对人可以相互看到。
思路
我们可以维护一个单调递减栈，然后分情况讨论一下。
- 如果要入栈元素大于当前元素，那么当前元素和入栈元素是可以相互看见的，因为这是找了左边区间第一个比它小的元素了，然后因为这是一个单调递减栈，所以我们可以一直出栈比入栈元素小的元素，可以发现这些都是可以互相看见的。而且最终的栈顶元素和要入栈元素也是可以看见的。
- 如果入栈元素小于当前元素，他可以和栈顶元素看见，而不能和后面的人看见，因为栈顶元素挡住他了。
- 如果入栈元素和当前元素高度相同，那么他们俩其实是等效的，如果有人比他们高，其实是可以直接看见两个，所以我们只需要将他们看成一个结构体，记录他们的数量和高度即可，每次统计的时候加上数量就行。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=500005;
int n;
int h[maxn];
ll ans;
struct node
{
ll cnt; // num
ll p; //height
}stack[maxn];
int top;
int main()
{
// freopen("test.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=1;i<=n;i++)
{
node temp;
temp.cnt=1;
temp.p=h[i];
while(top>=0&&h[i]>stack[top].p)
{
ans+=stack[top].cnt;
top--;
}
if(h[i]==stack[top].p)
{
ans+=stack[top].cnt;
temp.cnt+=stack[top].cnt;
top--;
}
stack[++top].cnt=temp.cnt;
stack[top].p=temp.p;
if(top!=0) ans+=1;
}
printf("%lld",ans);
}