题目描述
给出一张n * m的矩阵,求出全部标记为为F的最大矩形面积s,输出s * 3
数据范围
$1 <= n,m <= 1000$
输入样例
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
输出样例
45
预处理每个位置可向上扩展的高度$h$(连续F的个数)
接下来就是 $n$ 次 Acwing.131直方图中最大的矩形
把每一行作为下底边,利用单调栈求出可向左右两边扩展的宽度$r - l + 1$,
并用这个 $h * (r - l + 1)$ 更新最大面积
时间复杂度 $O(n^2)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
bool map[N][N];
int h[N][N];
int n, m;
int q[N], l[N], r[N];
int res;
int f(int h[])
{
h[0] = 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;
}
tt = -1;
q[++ tt] = m + 1;
for(int i = m; i; i --)
{
while(h[q[tt]] >= h[i]) tt --;
r[i] = q[tt] - i;
q[++ tt] = i;
}
for(int i = 1; i <= m; i ++) res = max(res, h[i] * (l[i] + r[i] - 1));
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
char s[2];
scanf("%s", s);
if(s[0] == 'F') map[i][j] = true;
}
for(int j = 1; j <= m; j ++)
{
int d = 0;
for(int i = 1; i <= n; i ++)
{
if(map[i][j]) d ++;
else d = 0;
h[i][j] = d;
}
}
for(int i = 1; i <= n; i ++) f(h[i]);
printf("%d", res * 3);
return 0;
}