定义
具有单调性的栈结构，该数据结构的目的是快速找到与一个元素距离最近的元素
过程（摘自oiwiki）
插入
将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。
例如，栈中自顶向下的元素为 {0,11,45,81}。
插入元素 14 时为了保证单调性需要依次弹出元素 0,11，操作后栈变为 {14,45,81}。
每个元素都只入栈一次，出栈一次，时间复杂度是o(n)
接下来看一些例题了解一下具体写完与应用
例题1 求下一个最大的数（单调栈例题）
给你 n 个整数 a1,a2,…,an，请问从每个数字往后看，第一个比它大的数字的下标是多少？如果后面没有比它大的数字，则输出 0。
输入格式
第一行一个整数 n。接下来一行 n 个整数 a1,a2,…,an。
输出格式
输出一行 n 个整数，表示答案。样例输入
7
2 6 3 1 5 7 4
样例输出
2 6 5 5 6 0 0
数据规模
对于 100% 的数据，保证 1≤n≤2×105,1≤ai≤109。
从后往前做一遍单调栈就行，保证栈是单调递减的
代码
# include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int hh = 0;
int st[N]; //单调栈数组
int a[N];
int ans[N]; //记录a[i]的下一个比他大的数的下标
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>0;i--)
{
while(hh && a[i]>=a[st[hh]]) hh--; //当栈不为空，或者栈顶元素小于a[i]的时候将栈顶元素弹出
ans[i] = st[hh]; //题目要求如果后面没有比它大的数字，则输出 0，正好栈为空的时候栈顶元素为0
st[++hh] = i; //将i入栈
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
例题2 最大矩形面积（典）
有一张 n 列的网格图，每列有一些格子被小蜗从底向上涂了色。现在给你每一列被涂色的格子的高度 ai，请你求出被涂色的格子组成的最大矩形的面积。
输入格式
第一行一个整数 n，表示总列数。接下来一行 n 个数 a1,a2,...,an。
输出格式
输出一行一个数，表示最大面积。样例输入
5
1 2 5 3 4
样例输出
9
样例解释
第 3、4、5 列可以组成 3×3 的矩形，面积为 9。数据规模
对于 100% 的数据，保证 1≤n≤2×105,1≤ai≤109。
思路是找到每个元素左右两边第一个比它小的元素，将左右两边这两个元素抛弃，中间的所有元素围成的矩形就是以当前元素高度为矩形高度所能围成的最大矩形。
从左往右，从右往左各做一遍单调栈，分别记录两边第一个比它小的元素的位置然后枚举就好。
复杂度o(n)
代码
# include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],l[N],r[N];
int st[N],tt = 0;
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
while(tt && a[st[tt]]>=a[i]) tt--;
l[i] = st[tt];
st[++tt] = i;
}
tt = 0;
st[0] = n+1;
for(int i=n;i;i--)
{
while(tt && a[st[tt]]>=a[i]) tt--;
r[i] = st[tt];
st[++tt] = i;
}
long long ans = 0;
for(int i=1;i<=n;i++) ans = max(ans,1ll*a[i]*(r[i]-l[i]-1));
cout<<ans;
return 0;
}
例题3 数对统计
给你 n 个数字 a1,a2,…,an，这些数字各不相同。询问共有多少对数字 (i,j) (1≤i<j≤n)，满足 ai 到 aj 中没有数字比 ai 或 aj 大。 即对所有位置 k (i<k<j)，满足 ak<min(ai,aj)。
输入格式
第一行一个整数 n。接下来一行 n 个整数 a1,a2,…,an。
输出格式
输出一行一个整数，表示答案。样例输入
5
2 5 4 6 3
样例输出
5
样例解释
符合要求的数对有 (1,2),(2,3),(2,4),(3,4),(4,5)。数据规模
对于 100% 的数据，保证 1≤n≤2×105,1≤ai≤109。
我们想要找到的其实是一个先减后增的区间。我们在维护一个递减单调栈的时候，新元素入栈会将小于它的元素踢掉，这个被踢掉的元素肯定是小于当前元素和当前栈内所有的元素，这就满足了一个先减后增的区间
所以每当新元素入栈的时候，每踢掉一个元素，答案+1就好了。
要注意的是，当栈内只剩一个元素的时候，那么无法形成所需要的区间，答案不会变化，这里需要特判一下
代码
# include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],st[N],tt = 0;
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans = n-1;
for(int i=1;i<=n;i++)
{
while(tt && a[st[tt]]<=a[i])
{
tt--;
if(tt && st[tt]!=i-1) ans++;
}
st[++tt] = i;
}
cout<<ans;
return 0;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
