单调栈的经典应用,求直方图最大面积的经典应用
做题顺序:单调栈->求直方图最大面积->城市游戏->最大面积acwing3516
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N][N]; // 直方图
char g[N][N];
int l[N], r[N], q[N];
int n, m;
int cal(int s[], int n) {
s[0] = s[n + 1] = -1;
int tail = 0;
q[tail] = 0;
for (int i = 1; i <= n; i++) {
while (s[q[tail]] >= s[i]) tail--;
l[i] = i - q[tail];
q[++tail] = i;
}
tail = 0;
q[tail] = n+1;
for (int i = n; i >= 1; i--) {
while (s[q[tail]] >= s[i]) tail--;
r[i] = q[tail] - i;
q[++tail] = i;
}
int res = 0;
for (int i = 1; i <= n; i++) {
res = max(res, (r[i] + l[i] - 1) * s[i]);
}
return res;
}
int init() {
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == 'F') s[i][j] = s[i-1][j] + 1;
else s[i][j] = 0;
}
res = max(res, cal(s[i], m));
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
cout << init() * 3 << endl;
return 0;
}