AcWing 152. 城市游戏
原题链接
中等
作者:
自说i
,
2024-01-21 12:19:30
,
所有人可见
,
阅读 37
将二维的转化一维的,利用单调栈解决重复的最大矩形面积问题
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int height[N],n,m,ans;
int arr[N][N],stk[N],top;
int main()
{
char x;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>x;
if(x=='R') arr[i][j]=0;
else arr[i][j]=1;
}
}
height[0]=0;
height[m+1]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(arr[i][j]!=0)
{
height[j]+=arr[i][j];
}
else height[j]=0;
}//每次动态的维护高度数组,将二维的变成一维的累加
//算出每次的高度数组的最大面积,并维护
for(int i=0;i<=m+1;i++)
{
while(top&&height[stk[top]]>=height[i])
{
int loc=stk[top];
top--;
int width=i-stk[top]-1;
ans=max(ans,width*height[loc]);
}
stk[++top]=i;
}
}
cout<<ans*3<<endl;
}