单调栈学习记录
程序员文章站
2022-04-01 17:55:54
...
单调栈问题
1,单调递增栈(入栈顺序)
https://blog.csdn.net/lucky52529/article/details/89155694
我是从这里学的吼
例题:积水面积(洛谷P1318)
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,gao;
}a[10500];
stack<node>P;
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].gao);
a[i].x=i;
}
P.push(a[1]);
int ans=0;
for(int i=2;i<=n;i++)
{
node past=P.top();
if(past.gao<=a[i].gao)
{
while(!P.empty()&&past.gao<=a[i].gao)
{
int di=past.gao;
P.pop();
if(P.empty())
{
break;
}
past=P.top();
ans+=(min(a[i].gao,past.gao)-di)*(a[i].x-past.x-1);
//cout<<" di: "<<di<<endl;
//cout<<"I: "<<i<<" "<<a[i].gao<<" x: "<<past.x<<" "<<past.gao<<" S: "<<(min(a[i].gao,past.gao)-di)*(a[i].x-past.x-1)<<endl;
}
P.push(a[i]);
}
else if(past.gao>a[i].gao)
{
P.push(a[i]);
}
}
cout<<ans<<endl;
while(!P.empty())
{
P.pop();
}
return 0;
}
2,单调递减栈
例题:麻烦的杰西 最大矩形面积
//https://ac.nowcoder.com/acm/contest/3402/B
#include <stack>
#include <iostream>
#include <cstdio>
using namespace std;
struct node
{
long long int x,gao;
}a[100500];
stack<node>P;
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].gao);
a[i].x=i;
}
a[n+1].gao=-1;
a[n+1].x=n+1;
P.push(a[1]);
long long int ans=0;
long long int h=0;
if(n==1)
{
cout<<a[1].gao<<" "<<a[1].gao<<endl;
continue;
}
for(int i=2;i<=n+1;i++)
{
node past=P.top();
if(P.empty()||a[i].gao>=past.gao)
{
P.push(a[i]);
}
else
{
while(!P.empty()&&P.top().gao>a[i].gao)
{
past=P.top();
P.pop();
long long int temp=(long long int)(a[i].x-past.x)*past.gao;
//cout<<"i: "<<i<<" "<<a[i].gao<<" x: "<<past.x<<" "<<past.gao<<" t: ”<<temp<<endl;
if(temp>=ans)
{
ans=temp;
h=past.gao;
}
}
a[i].x=past.x;
P.push(a[i]);
}
}
cout<<h<<" "<<ans<<endl;
}
return 0;
}```
上一篇: 1127. 多边形面积(计算几何)
下一篇: 计算几何——多边形面积