解题思路基于131题直方图矩形的最大面积,利用单调栈去计算最大的面积,该题可以理解为每加入一个新的行就会多出一种新的直方图情况,重新求取直方图矩形的最大面积即可,再从这些每一行的最大矩形中选出最大的矩形就是答案
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 1010;
int n, m;
char num[N][N];
int h[N][N];
int q[N], l[N], r[N];
long long int work(int *h)
{
int index = 0;
q[0] = 0;
for(int i = 1;i <= m;i++)
{
while(h[i] <= h[q[index]])
index--;
l[i] = q[index];
q[++index] = i;
}
index = 0;
q[0] = m + 1;
for(int i = m;i >= 1;i--)
{
while(h[i] <= h[q[index]])
index--;
r[i] = q[index];
q[++index] = i;
}
long long int ans = 0;
for(int i = 1;i <= m;i++)
{
ans = max(ans, (long long int)h[i] * (r[i] - l[i] - 1));
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
getchar();
for(int i = 1; i <= n;i++)
{
for(int k = 1;k <= m;k++)
{
h[i][0] = -1;
scanf("%c", &num[i][k]);
if(num[i][k] == 'F')
{
h[i][k] = h[i - 1][k] + 1;
}
else
{
h[i][k] = 0;
}
getchar();
}
h[i][m + 1] = -1;
}
long long int ans = 0;
for(int i = 1;i <= n;i++)
{
ans = max(ans, work(h[i]));
}
cout << 3 * ans << endl;
return 0;
}