“二维”单调栈的题目，一上来有点没有思路，想用dp做一下，然而转念一想，假设我们把这个图按照行进行划分，先处理前1行的最大矩形，在处理前2行的最大矩形，再处理前3行的最大矩形……最后用子问题的答案更新答案即可。这样一来，这个问题就转化成了一个简化版单调栈的题目。
简化版点这里，所以，我们采用这种思路即可得出答案，时间复杂度为简化版的n倍（相当于做了n次单调栈），在n≤1000时可以通过。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 int n,m,a[1010][1010],b[1010],s[1010],p,ans,w[1010]; 8 int main() { 9 cin>>n>>m; 10 for(int i=1;i<=n;i++) 11 for(int j=1;j<=m;j++) { 12 char c; 13 cin>>c; 14 a[i][j]=c==‘F‘; 15 } 16 for(int i=1;i<=n;i++) { 17 for(int j=1;j<=m;j++) 18 b[j]=a[i][j]?b[j]+1:0; 19 p=0; 20 for(int j=1;j<=m+1;j++) { 21 if(b[j]>s[p]) s[++p]=b[j],w[p]=1; 22 else { 23 int tot=0; 24 while(s[p]>b[j]) { 25 tot+=w[p]; 26 ans=max(ans,tot*s[p]); 27 p--; 28 } 29 s[++p]=b[j]; 30 w[p]=tot+1; 31 } 32 } 33 } 34 cout<<ans*3<<endl; 35 return 0; 36 }
原文：https://www.cnblogs.com/shl-blog/p/10885867.html
