C++ 容器类 <queue> | 菜鸟教程
C++ 容器类 <deque> | 菜鸟教程
C++ 容器类 <priority_queue> | 菜鸟教程

队列是一种先入先出的数据结构，就像排队
单调队列就是具有单调性的特殊队列
deque是双端队列
优先队列，可以自动排序，默认是大根堆（队首元素是最大值）

// 声明队列
queue<Type> q;
//检查队列是否为空
empty();
//返回队列中的元素数量
size();
//返回队首元素的引用
front();
//返回队尾元素的引用
back();
//在队尾添加一个元素
push();
//移除队首元素
pop();//pop_front();

//声明双端队列
deque<Type> q;
//检查队列是否为空
empty();
//返回队列中元素个数
size();
//返回队首元素
front();
//返回队尾元素
back();
//抛出队首元素，抛出队尾元素
pop_front();pop_back();

//声明优先队列
peiority_queue<int>qe;//默认大根堆
peiority_queue<int,vector<int>,compare>qe;//可自定义是大根堆还是小根堆
// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q; 

empty(): 检查队列是否为空。
size(): 返回队列中的元素数量。
top(): 返回队列顶部的元素（不删除它）。
push(): 向队列添加一个元素。
pop(): 移除队列顶部的元素。

滑动窗口

AcWing 154. 滑动窗口—海绵宝宝来喽 – AcWing

/*
给定一个大小为 n≤10^6的数组。
有一个大小为 k的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k个数字。
每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k为 3

窗口位置	     最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式
输入包含两行。
第一行包含两个整数 n和 k,分别代表数组长度和滑动窗口的长度。
第二行有 n个整数，代表数组的具体数值。
同行数据之间用空格隔开。

输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    deque<int>qe;//双端队列方便从两段进行操作
    for(int i=0;i<n;i++){
        while(!qe.empty()&&qe.back()>a[i])qe.pop_back();
        qe.push_back(a[i]);
        if(i+1>=k)cout<<qe.front()<<" ";
        if(i+1>=k&&qe.front()==a[i+1-k])qe.pop_front();
    }
    qe.clear();
    cout<<endl;
    for(int i=0;i<n;i++){
        while(!qe.empty()&&qe.back()<a[i])qe.pop_back();
        qe.push_back(a[i]);
        if(i+1>=k)cout<<qe.front()<<" ";
        if(i+1>=k&&qe.front()==a[i+1-k])qe.pop_front();
    }
    return 0;
}

找最小值时队列单调递增，从队列后面比较把比当前数大的数抛出，然后把这个数放进去，因为单调递增所以队列的队首是当前最小的值，找最大值时同理