基础算法——单调栈和单调队列的最常用考法

单调栈和单调队列虽然有点抽象但在算法题中很少涉题。

单调栈常见的最可能考的就是：给定一个序列，求序列当中每一个数左边离他最近的数，且比他小(大)的数在什么地方，对称下就可类比为右边最近比他（大或小的数）。

首先想到暴力做法；两重循环，i枚举每个数，j从 i-1开始往左边找第一个比a[i]小的，时间复杂度为O(n2),很大可能会超时。

单调栈优化的话：i指针每往右边移动时，把每个数存到栈里，把目光放到栈里，将数在栈中操作，这样每个数操作一次就行了，整体时间复杂度就是O(n)

具体题目要求：
给定一个长度为 N
的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1

#include<iostream>

using namespace std;

const int N = 100010;
int st[N];//模拟栈
int tt;//栈尾指针

int main(){
    
    int n;//长度为n的数列
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        int x;
        scanf("%d",&x);//输入次数，目的是找到左边第一个比他小的数
        
        //当栈不为空且栈顶元素大于等于次数时，出栈。直到栈顶元素小于次数，栈顶元素即为所求
        while(tt && st[tt] >= x)tt--;
        
        if(tt > 0) printf("%d ",st[tt]);
        else printf("-1 ");
        //求出此次比他小的数后，将该数也添加到栈中
        st[++tt] = x;
    }
    return 0;
}

单调队列应用最典型的问题就是：滑动窗口：求窗口中的最大值或最小值输出。

#include<iostream>

using namespace std;

const int N = 1000010;

int a[N],q[N];
//a数字存储元素，q数组存储下标
int n,k;
int main(){

    scanf("%d %d" ,&n,&k);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    //最窗口最小值
    int hh = 0, tt = -1;
    for(int i = 0; i < n; i++){

        while(hh <= tt && i-k+1 > q[hh])hh++;

        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if(i >= k -1) printf("%d ",a[q[hh]]);
    }
    puts("");

    //求窗口最大值
    hh = 0, tt = -1;
    for(int i = 0; i < n; i++){
        while(hh <= tt && i-k+1 > q[hh])hh++;

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

}