栈与队列：单调队列、单调栈

栈和队列的基本操作

算法思想

1. 栈：先进后出
2. 队列：先进先出

模板代码

#include<iostream>
using namespace std;
const int N = 1e5 +10;
int stk[N],tt = 0;          //tt表示栈顶下标,初始时为0
// ********************** 栈
//插入
stk[ ++ tt] = x;

//弹出
tt --;

//判断栈是否为空
if(tt > 0) not empty
else empty

//栈顶
stk[tt];
// ********************** 队列
//队尾插入元素，队头弹出元素
int q[N],hh,tt = -1;         //hh表示队头，tt表示队尾初始时为-1

//插入
q[++ tt] = x;

//弹出
hh ++;

//判断队列是否为空
if(hh <= tt) not empty
else empty

//取出队头元素
q[hh];

单调栈

问题描述

1. 给定一个序列，求出在这个序列当中，每一个数离他左边最近的数且比它小的数在什么地方，不存在返回-1
2. 单调递增栈： 从栈顶往栈底看，是单调递增的关系（含相等）
3. 单调递减栈： 从栈顶往栈底看，是单调递减的关系（含相等）
4. 

完整代码

//单调栈
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int stk[N],tt;

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

单调队列

算法思想

1. 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最小值

完整代码

//单调队列
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
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]);
    int hh = 0,tt = -1;
    for(int i = 0;i < n;i ++){
        //判断队头是否已经滑出窗口
        if(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 ++){
        //判断队头是否已经滑出窗口
        if(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]]);
    }
    return 0;
}