博客

单调栈普通的栈的区别就是单调栈里面的元素数值大小是严格的单调上升或者是单调下降的

同时队列也是一样的情况

那我们怎么实现和在相应题目中解题呢？

首先先看到单调栈

比如给出下面这一个题目

给出一个长度为N的数列，求出每个数左边第一个比它小的数，如果不存在则输出”-1″，执行M次

比如给出3    4    2    7    5

要怎么输出呢？

如果要用暴力解法的话，可能就是两重循环，这样的话时间复杂度太高了

那有没有更简单的方法呢？当然有！！！

用我们学过的栈来解决，首先我们先创一个元素为0的栈，然后再拿栈顶元素和要求的值比较，如果栈顶元素更小，就直接输出栈顶元素既可，然后再把当前比较的值压入栈内

如果不符合，就把栈顶元素删除再比较，直至栈内元素为0，则输出”-1″。再把该元素入栈

具体代码如下

const int N=100010;

int n;
int skt[N],tt;

int main()
{
    scanf("%d",&n);
    
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        
        while(tt&&skt[tt]>=x) tt--;
        if(tt) cout<<skt[tt]<<' ';
        else cout<<-1<<' ';
        
        skt[++tt]=x;
    }
    return 0;
}

单调队列：

还是老办法，直接给出题目，在做题目中分析

比如给出一个长度为N的数列，再给出一个长度为k的滑动窗口，它从数组的最左边滑到数组的最右边，窗口每一次只能向右滑动一个位置，求出每次在窗口里面的最大值和最小值

首先我们先求出每次在窗口里面的最小值

首先给出一段数列

1    3    -1    -3    5    3    6    7

首先要窗口里面的数一开始满足k才能开始输出

那我们要怎么求呢，首先和栈一样，先比较队尾元素和要比较的元素，如果队尾元素更小的话，则输出队首元素，入队。因为是单调上升的。如果队尾元素更大的话，就删除，再比较下一个，直至为0，如果为0，则输出该元素，在入队。

求最大值刚好相反就可以了，代码具体如下

const int N=1000010;

int hh,tt=-1;
int n,k;
int a[N],q[N];

int main()
{
    scanf("%d%d",&n,&k);
    
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-q[hh]+1>k) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        if(i+1>=k) printf("%d ",a[q[hh]]);
    }
    puts("");
    
    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-q[hh]+1>k) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i+1>=k) printf("%d ",a[q[hh]]);
    }
    
    return 0;
}