830. 单调栈

https://www.acwing.com/problem/content/832/
思路：维护一个严格递增的栈,由于题目是找小于的值.所以如果栈顶元素比当前元素大,就后续不会再被用到可直接弹出

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int stk[N],tt;
int a[N];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
        while(tt && stk[tt]>=a[i]){
            tt--;
        }
        if(tt) cout<<stk[tt]<<" ";
        else cout<<"-1 ";
        stk[++tt]=a[i];
    }

  return 0;
}
//  freopen("testdata.in", "r", stdin);

131. 直方图中最大的矩形

https://www.acwing.com/problem/content/description/133/
确定面积的条件就是左右边和高度,
高度题目已经给了,左右边实际上就可以转化成向左右找到第一个小的下标

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int l[N],r[N],h[N],q[N];

int main(){
    int n;
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;i++){
            scanf("%d",&h[i]);
        }
        h[0]=h[n+1]=-1;
        int tt=0;
        q[0]=0;
        for(int i=1;i<=n;i++){
            while(h[i]<=h[q[tt]]){
                tt--;
            }
            l[i]=q[tt];
            q[++tt]=i;
        }
        tt=0;
        q[0]=n+1;
        for(int i=n;i>=1;i--){
            while(h[i]<=h[q[tt]]) tt--;
            r[i]=q[tt];
            q[++tt]=i;
        }
        LL res=0;
        for(int i=1;i<=n;i++){
            res=max(res,(LL)h[i]*(r[i]-l[i]-1));
        }
        cout<<res<<endl;
    }
  return 0;
}
//  freopen("testdata.in", "r", stdin);

比起上面复杂了点。

152. 城市游戏

https://www.acwing.com/problem/content/154/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=1005;
int n,m;
char a[N][N];
int h[N][N],l[N],r[N],q[N];
void cal(int a[], int l[])
{
    int hh = 0, tt = 0;
    a[0] = -1;
    for (int i = 1; i <= m; i ++ )
    {
        while (a[q[tt]] >= a[i]) tt -- ;
        l[i] = q[tt] + 1;
        q[ ++ tt] = i;
    }
}
int work(int a[]){
    cal(a, l);
    reverse(a + 1, a + 1 + m);
    cal(a, r);
    reverse(a + 1, a + 1 + m);
    int res = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int left = l[i];
        int right = m + 1 - r[m + 1 - i];
        res = max(res, a[i] * (right - left + 1));
    }

    return res;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]==‘F‘) h[i][j]=h[i-1][j]+1;
            else h[i][j]=0;
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,work(h[i]));
    }
    cout<<res*3<<endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

单调栈 及其应用

原文：https://www.cnblogs.com/OfflineBoy/p/14778403.html