单调栈
介绍与问题背景
正如其名,单调栈,具有单调性,这里的单调的含义有两层
-
在栈中的元素具有单调性,元素要么单调递增,要么单调递减,因此,栈顶元素必然是最值(最大值,或最小值)
-
且栈中元素是下标也是单调的,从栈底到栈顶,是按照元素下标顺序逐渐增大,出现这个是很自然但是容易被忽略。
因为是遍历,所以第二个条件天然满足。
那么为了满足第一个条件就要不断将当前元素
与栈顶元素
进行比较,只要大于等于都要出栈。
这样不仅保证了最值,而且可以做到,最近的第一个。
首先我们在看这样一个问题
3 4 2 7 5
给定这样一个序列,求每个数左边
的第一个
比它小的数
问题模拟
我们选定第5个数5。
因为是5的左边,且第一个,我们需要按从7开始,按顺序一个接一个比较。遇到第一个比它小的数返回。
我们发现如果这样作,对于每个数,都需要遍历一遍它前面的数,时间复杂度为$o(n^2)$
可不可以优化呢?
答案是可以,使用单调栈可以优化到$o(n)$
常用模型:找出每个数左边离它最近的比他大(小)的数
那么我只用一个内存单位,记录之前的最小值,可不可以呢?
不行
,我们找的不是最小值,而是第一个最小值。
那我们就在想如何找一个数据结构可以把我们之前遍历的信息保存下来。
单调栈
在一遍的遍历的过程中,在每个元素入栈前,要把栈顶大于它的,也就是它左边大于它的数全部出栈,想一想为什么呢🤔️。
因为如果当前数不是左边最小的值,那么左边大于它的数必然不可能是最小值。
一些细节
- 手动模拟栈时,当tt=0时代表此时栈为空。
- 每一个元素都是要入栈的
- 代码中$\ge$中的
等于
非常重要,即使是相等也不行,必需是小于的第一个数。
应用一: 维护单调序列
int stk[N],tt;
while(n--)
{
int x;
scanf("%d",&x);
//因为是第一个比他小的数
//那么大于等于当前数的栈顶,都要弹出
while(tt&&stk[tt]>=x) tt--;
if(!tt) printf("-1 ");
else printf("%d ",stk[tt]);
stk[++tt] = x;
//入栈
}
应用二:最大矩形
在栈中可以存值
也可以存下标
区间最值
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int h[N],q[N],l[N],r[N];
typedef long long LL;
int main()
{
int n;
while(scanf("%d",&n),n)
{
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
int tt = 0;
//为了比较栈顶为-1
h[0]=-1;
q[0]=0;
//栈顶一定不会弹出
//我们这里需要的是下标,而不是高度
for(int i=1;i<=n;i++)
{
while(h[q[tt]]>=h[i]) tt--;
//单调栈求出来的是最近
l[i]=q[tt];
q[++tt]=i;
}
//从右往左枚举
tt = 0;
h[n+1]=-1;
q[0]=n+1;
for(int i=n;i;i--)
{
while(tt&&h[q[tt]]>=h[i]) tt--;
//如果为0,下标是它本身
r[i]=q[tt];
q[++tt]=i;
}
LL res = 0;
for(int i=1;i<=n;i++) res = max(res,(LL)h[i]*(r[i]-l[i]-1));
cout<<res<<endl;
}
return 0;
}
Hard:预处理优化➕单调栈
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m;
char g[N][N];
int l[N], r[N], q[N];
int U[N], D[N], L[N], R[N];
int s[N][N];
int calc(int h[],int n)
{
//高度矩阵和宽
h[0]=h[n+1]=-1;
int tt = 0;
q[0]=0;
for(int i=1;i<=n;i++)
{
while(h[q[tt]]>=h[i]) tt--;
l[i]=q[tt];
q[++tt]=i;
}
tt = 0;
q[0]=n+1;
for(int i=n;i;i--)
{
while(h[q[tt]]>=h[i]) tt--;
r[i]=q[tt];
q[++tt]=i;
}
int res = 0;
for(int i=1;i<=n;i++)
res = max(res,h[i]*(r[i]-l[i]-1));
return res;
}
void init()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
if(g[i][j]=='1') s[i][j]=s[i-1][j]+1;
else s[i][j]=0;
U[i]= max(U[i-1],calc(s[i],m));
}
memset(s,0,sizeof s);
for(int i=n;i;i--)
{
for(int j=1;j<=m;j++)
if(g[i][j]=='1') s[i][j]=s[i+1][j]+1;
else s[i][j]=0;
D[i]=max(D[i+1],calc(s[i],m));
}
memset(s,0,sizeof s);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
if(g[j][i]=='1') s[i][j]=s[i-1][j]+1;
else s[i][j]=0;
L[i]=max(L[i-1],calc(s[i],n));
}
memset(s,0,sizeof s);
for(int i=m;i;i--)
{
for(int j=1;j<=n;j++)
if(g[j][i]=='1') s[i][j]=s[i+1][j]+1;
else s[i][j]=0;
R[i]=max(R[i+1],calc(s[i],n));
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",g[i]+1);
init();
int Q;
scanf("%d",&Q);
while(Q--)
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
printf("%d\n",max(max(U[x-1],D[x+1]),max(L[y-1],R[y+1])));
}
return 0;
}
支持一下