Acwing基础课——单调栈

2021-03-18

基础模板

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;
    }
};

标题:Acwing基础课——单调栈
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/03/18/1616040872873.html