本文最后更新于 33 天前,其中的信息可能已经有所发展或是发生改变。
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;
}
找最小值时队列单调递增,从队列后面比较把比当前数大的数抛出,然后把这个数放进去,因为单调递增所以队列的队首是当前最小的值,找最大值时同理