基础模板

1、单调栈

题意：

找出每个元素左边第一个比其小的数，如果没有输出-1；

思路

例如a[3],a[5]，假设a[3]>=a[5]，那么a[3]永远不会作为答案输出，所以维护一个单调递增栈即可。

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int stk[N];
int h[N];
int l[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>h[i];
    }
  
    h[0]=h[n+1]=-1;
  
    int tt=0;
    for(int  i=1;i<=n;i++){
        while(h[stk[tt]]>=h[i]) tt--;
      
        l[i]=stk[tt];
        stk[++tt]=i;
    }
  
    for(int i=1;i<=n;i++) {
        cout<<h[l[i]]<<' ';
    }
    return 0;
}

1793. 好子数组的最大分数

3194. 最大的矩形

思路：
维护两个单调栈，一个左边比起小的元素，一个右边比起小的元素。计算时对于当前元素，找出左边的比起小的元素坐标，与右边比起小的元素下标，计算长度从而更新最大面积。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int stk[N];
int h[N];
int l[N];
int r[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++ ){
        cin>>h[i];
    }
    h[0]=h[n+1]=-1;
    int tt=0;
  
    stk[0]=0;
    for(int i=1;i<=n;i++) {
        while(h[stk[tt]]>=h[i]) tt--;
      
        l[i]=stk[tt];
        stk[++tt]=i;
     //   cout<<l[i]<<' ';
    }
   // puts("");
    tt=0;
    stk[0]=n+1;
    for(int i=n;i>=1;i--) {
        while(h[stk[tt]]>=h[i]) tt--;
      
        r[i]=stk[tt];
        stk[++tt]=i;
       // cout<<r[i]<<' ';
    }
  
    int res=0;
    for(int i=1;i<=n;i++) {x
        res=max(res,(r[i]-l[i]-1)*h[i]);
    }
    cout<<res<<'\n';
    return 0;
  
  
}

456. 132 模式

题意：找出满足$ a[i]<a[k]<a[j]$且满足$i<j<k$的数

思路：
单调栈预处理出每个数左边第一个比起大的数，再从头扫描记录每个数左边比起最小的数，对于每个数判断如下条件:左边第一个比起大的数是否存在，若存在该数即可当成中间数，再向前找前面比起最小的数，若次数小于枚举的最右边的数则输出True，反之输出False

代码：

const int N=1e5+10;
int h[N];
int stk[N];
int l[N];
int mi[N];
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int len=nums.size();

        int tt=0;
        memset(stk,0,sizeof stk);
        for(int i=0;i<len;i++) {
            h[i+1]=nums[i];
        }
        h[0]=0x3f3f3f3f;
        cout<<h[0]<<'\n';
        //找左边第一个比起大的数
        for(int i=1;i<=len;i++) {
            while(h[stk[tt]]<=h[i])tt--;
            l[i]=stk[tt];
            stk[++tt]=i;
        }

        //记录每个数左边比起最小的数
        int mix=0x3f3f3f3f;
        for(int i=1;i<=len;i++) {
           if(mix<h[i])mi[i]=mix;
           else mi[i]=0x3f3f3f3f;
           mix=min(mix,h[i]);
        }
        int f=0;
        for(int i=1;i<=len;i++) {
            int m=l[i];
            if(!m||mi[m]==0x3f3f3f3f) continue;
            if(mi[m]<h[i]) return true;
        }
        return false;
    }
};