队列、单调队列
本文最后更新于 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;
}

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

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇