單調棧學習筆記

?線性結構——單調棧

①定義：棧內的元素，按照某種方式排序（單調遞增或單調遞減）如果新入棧的元素破壞了單調性，就彈出棧內元素，直到滿足單調性

②優點：可以很方便地求出某個數左邊或者右邊第一個比他大或者小的元素，總時間復雜度為O(n)

③如何維護單調棧（以遞增為例）

進棧操作：每次入棧前先檢驗棧頂元素和進棧元素x的大小，如果小于x，就讓x
???? 直接入棧。如果棧頂元素大于等于x，那么出棧，直到棧空或者棧頂元素小于x。
??? ?
【例1】最大矩形面積(poj2559)

#include<bits/stdc++.h>
using namespace std;
const int N=100002;
int h[N],n;
int line[N],L[N],R[N],top=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    for(int i=1;i<=n;i++){
        while(top&&h[line[top]]>=h[i]) top--;
        L[i]=top?line[top]+1:1;
        line[++top]=i;
    }
    top=0;
    for(int i=n;i>=1;i--){
        while(top&&h[line[top]]>=h[i]) top--;
        R[i]=top?line[top]-1:n;
        line[++top]=i;
    }
    int maxn=0;
    for(int i=1;i<=n;i++){
        int ans=h[i]*(R[i]-L[i]+1);
        maxn=max(maxn,ans);
    }
    cout<<maxn<<endl;
    return 0;
}

?

【例2】玉蟾宮(luogu P4147)

題目傳送門

講一講我自己的思路(其實是同學教的)吧，似乎不是很好的解？但我感覺比較好理解……

首先把輸入的字符矩陣轉移為數字，即s[i][j]代表第i行第j列這一格上面連續的F的個數(如果這一格是S的話就是0)，所以預處理之后就把樣例變成了這樣：

0 1 1 1 1 1

1 2 2 2 2 2

0 0 0 3 3 3

1 1 1 4 4 4

2 2 2 5 5 5

代碼實現：

for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){char ch;cin>>ch;if(ch=='F') s[i][j]=s[i-1][j]+1;}

然后就有點類似于上面那道題了，每一行分開分析，找到每一個位置可以向左右擴展的最長的長度，這是矩形的長，而組成的矩形的寬就是這一格中對應的數字，所以向左右兩邊擴展的條件就是要擴展的那一格中的數字一定大于等于當前掃描到的這一格的數字。(似乎沒太講清楚啊QAQ)每一行處理出一個可以組成的矩形的最大面積，用一個maxn取最大值就可以找到最后的答案了。

代碼實現：

for(int i=1;i<=n;i++){int ans=0;//用于記錄當前這一行的矩形最大面積for(int j=1;j<=m;j++){int l=j,r=j;//l代表左邊能擴展到的最遠位置，r代表右邊能擴展到的最遠位置while(l>=1&&s[i][l]>=s[i][j]) l--;l++;while(r<=m&&s[i][r]>=s[i][j]) r++;r--;ans=max(ans,s[i][j]*(r-l+1));//當前這一行的最大矩形面積
    }maxn=max(ans,maxn);//每一行的最大矩形面積比較取最大值
}

以下完整代碼(沒開O2的時候T了兩個點QAQ)

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1002;
int K,n,m;
int s[N][N];
int maxn=0;
int max(int x,int y){
    return x>y?x:y;
}
int main(){
    //scanf("%d",&K);
    //while(K--){
        memset(s,0,sizeof(s));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                char ch;
                cin>>ch;
                if(ch=='F') s[i][j]=s[i-1][j]+1;
            }
        for(int i=1;i<=n;i++){
            int ans=0;//用于記錄當前這一行的矩形最大面積
            for(int j=1;j<=m;j++){
                int l=j,r=j;//l代表左邊能擴展到的最遠位置，r代表右邊能擴展到的最遠位置
                while(l>=1&&s[i][l]>=s[i][j]) l--;
                l++;
                while(r<=m&&s[i][r]>=s[i][j]) r++;
                r--;
                ans=max(ans,s[i][j]*(r-l+1));//當前這一行的最大矩形面積
            }
            maxn=max(ans,maxn);//每一行的最大矩形面積比較取最大值
        }
        printf("%d\n",maxn*3);//最后別忘了乘3
    //}
    return 0;
}

?