因为没有地方打卡写笔记 所以写了个这个
上一题
题目描述
blablabla
单调栈
本题的每一行都是一道直方图,求每一行的最大面积,再从中取出所有行的最大面积。
时间复杂度
建图O(nm) 求值O(nm) 所以总的时间复杂度为O(n*m)
C++ 代码
#include<iostream>
/*单调栈,每一行都看成上一道直方图的题 求每一行的最大面积,再从中取出所有行的最大面积 */
using namespace std;
const int maxn = 1010;
int h[maxn];
int l[maxn];
int r[maxn];
int q[maxn];
char g[maxn][maxn];
int n,m;
void get(int a[])
{
for(int i=1;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
}
// Cal(i) 求第i行的直方图最大面积
int Cal(int i)
{
//l[],r[]都不用memset,因为会覆盖
//h不能覆盖 因为要积累
//初始化高度数组
for(int j=1;j<=m;j++)
{
if(g[i][j]=='F') h[j]+=1; //用一维数组即可
else h[j]=0;
}
// get(h);
// 单调栈
//从左向右单增
h[0]=-1;
h[m+1]=-1;
int tt=-1;
q[++tt]=0;
for(int i=1;i<=m;i++)
{
while(h[q[tt]]>=h[i]) tt--;
l[i]=i-q[tt];
q[++tt]=i;
}
// get(l);
//从右向左单调增
tt=-1;
q[++tt]=m+1;
for(int i=m;i>=1;i--)
{
while(h[q[tt]]>=h[i]) tt--;
r[i]=q[tt]-i;
q[++tt]=i;
}
// get(r);
int res = 0;
for(int k=1;k<=m;k++) res=max(res,(r[k]+l[k]-1)*(h[k]));
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%s",&g[i][j]);
}
}
int ans = 0;
for(int i=1;i<=n;i++) //每行每行查
ans=max(Cal(i),ans);
cout<<(ans*3)<<endl;
return 0;
}