P4147 玉蟾宫
极简极短版速写单调栈
这里要找每个柱 左侧 以及 右侧 第一个比当前柱短的柱子的位置：
构建一个从栈顶到栈底的单调递减栈，只有想要入栈的元素大于栈顶元素时，才能入栈，否则栈顶元素出栈。
从左到右遍历，
栈顶元素出栈时 表明 栈顶元素找到了右边第一个小于它的柱子（的位置）；而且此时栈内 栈顶元素的前一个元素 是 当前栈顶元素左侧第一个小于它的元素
这样某个元素的左右侧第一个小于它的元素都找到了
栈顶元素连续出栈？上述过程照常举行。
在一次出栈时即可找到第一个比当前数小的数的位置，以及最后一个比当前数小的数的位置。
一次入栈出栈就解决题目不用从另一个方向遍历第二次
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int Map,stk;
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=Map+1;
// else Map=0;
}
while(top&&Map]>=Map){
int h=Map];
top--;
int l=top?stk:0;
ans=max(ans,(j-l-1)*h);
}
stk[++top]=j;
}
}
cout<<3*ans;
return 0;
} 确实是我颠末反复碰钉子+看题解后两个月后自己写出来的。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]