题目描述
在直方图最大面积
https://www.acwing.com/file_system/file/content/whole/index/content/2311109/
基础上再添加一层循环
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
const int N = 1010;
int n,m,h[N][N],l[N],r[N];
char map[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ){
char c;
cin >> c;
map[i][j] = c;
if(c == 'F')h[i][j] = h[i-1][j] + 1;
else h[i][j] = 0;
}
int res = 0;
//地基从第一层到最后一层
for (int i = 1; i <= n; i ++ )
{
h[i][0] = h[i][m+1] = -1;
//左边
stack<int> sl;
sl.push(0);
for (int j = 1; j <= m; j ++ ){
while(h[i][j] <= h[i][sl.top()])sl.pop();
l[j] = sl.top();
sl.push(j);
}
//右边
stack<int> sr;
sr.push(m+1);
for (int j = m; j > 0; j -- ){
while(h[i][j] <= h[i][sr.top()])sr.pop();
r[j] = sr.top();
sr.push(j);
}
for (int j = 1; j <= m; j ++ )
res = max(res,h[i][j] * (r[j]-l[j]-1));
}
cout << res*3 << endl;
return 0;
}