P4147 玉蟾宫

极简极短版速写

单调栈

这里要找每个柱 左侧 以及 右侧 第一个比当前柱短的柱子的位置：

构建一个从栈顶到栈底的单调递减栈，只有想要入栈的元素大于栈顶元素时，才能入栈，否则栈顶元素出栈。

从左到右遍历，

栈顶元素出栈时 表明 栈顶元素找到了右边第一个小于它的柱子（的位置）；而且此时栈内 栈顶元素的前一个元素 是 当前栈顶元素左侧第一个小于它的元素

这样某个元素的左右侧第一个小于它的元素都找到了

 

栈顶元素连续出栈？上述过程照常进行。

 

在一次出栈时即可找到第一个比当前数小的数的位置，以及最后一个比当前数小的数的位置。

一次入栈出栈就解决问题不用从另一个方向遍历第二次

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int Map[N][N],stk[N];
int n,m,top,ans;
char o;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){top=0;for(int j=1;j<=m+1;j++){if(j!=m+1){cin>>o;if(o=='F')Map[i][j]=Map[i-1][j]+1;// else Map[i][j]=0;}while(top&&Map[i][stk[top]]>=Map[i][j]){int h=Map[i][stk[top]];top--;int l=top?stk[top]:0;ans=max(ans,(j-l-1)*h);}stk[++top]=j;}}cout<<3*ans;return 0;
}

确实是我经过反复碰壁+看题解后两个月后自己写出来的。