一.概况queue函数今天主要学习了STL函数中的queue函数如何使用我在之前的博客中已经写过,在这里请点击下面让我们来看具体题目二.题目来源洛谷 P1886 P1714 P2058力扣 225牛客 NC50528三.题目具体分析1洛谷P1886 牛客[NC50528]这两道题一模一样这道题是一道标准的滑动窗口题运用队列只能在一段插入和在另一端删除从而获得窗口的最大值和最小值AC代码如下#includebits/stdc.h using namespace std; #define int long long signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,k; cinnk; int a[n1]; for(int i1;in;i)cina[i]; dequeintq; //求最小值 for(int i1;in;i){ //当前元素比队尾元素小删除队尾元素 while(!q.empty()a[i]a[q.back()])q.pop_back(); q.push_back(i);//入队 while(q.front()i-k)q.pop_front();//缩小滑动窗口确保窗口大小不超过k if(ik)couta[q.front()] ;//此时队首就是当前窗口最小值 } coutendl; q.clear();//清除 //求最大值 for(int i1;in;i){ //当前元素比队尾元素大删除队尾元素 while(!q.empty()a[i]a[q.back()])q.pop_back(); q.push_back(i);//入队 while(q.front()i-k)q.pop_front(); if(ik)couta[q.front()] ;//此时队首就是当前窗口最大值 } coutendl; return 0; }这道题相对好理解可以当做一个固定的滑动窗口模版来用。2洛谷P2058 海港核心条件输入的船只到达时间 t 严格递增关键天然满足滑动窗口单调性需求处理第 i 艘船时统计区间 (t - 86400 ,t] 所有乘客里不同国籍总数队列queue保存每一位乘客的 (到达时间t国籍x) 按到达先后排队计数数组/桶 cnt[] cnt[x] 当前窗口内国籍 x 的人数变量ans记录当前窗口不同国籍数量。完整流程每一艘船处理步骤读入当前船时间 t 、乘客数量 k 和所有乘客国籍将船上所有乘客 (t, x) 逐个压入队列如果 cnt[x]0 说明窗口新增国籍 ans cnt[x] 清理过期乘客窗口左端弹出循环判断队首乘客时间 q.front().t t - 86400 超出24小时取出队首国籍 x0 cnt[x0]-- 如果 cnt[x0]0 这个国籍没人了 ans-- 队首弹出清理完成后直接输出 ans 。AC代码如下#includebits/stdc.husing namespace std;structnode{intx,t;}h;//定义结构体queuenodeq;//用于储存intans0,num[100005];intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;while(n--){intt,k;cintk;for(inti0;ik;i){intx;cinx;num[x];q.push({x,t});//入队if(num[x]1)ans;//出现新的国家总数加1}//清理过期记录滑动窗口核心for(hq.front();q.size()t-h.t86400;q.pop(),hq.front()){num[h.x]--;if(num[h.x]0)ans--;}coutansendl;}return0;}(3)洛谷P1714 切蛋糕题意给定长度 n 的数组求长度不超过 m 的连续子数组最大和。数据范围 n ≤ 5e5 需要 O(n) / O(n log n) 算法暴力枚举会超时。核心思路预处理前缀和数组 s s[0]0s[i] p₁p₂…pᵢ区间 [l,r] 和 s[r] - s[l-1]约束子数组长度 r-l1 ≤ m ⇒ l-1 ≥ r-m 。对固定右端点 r我们要找 r-m ≤ j ≤ r-1 范围内最小的 s[j]使得 s[r]-s[j] 最大。使用单调递增队列滑动窗口最小值维护队列保存 j 下标满足下标在区间 [r-m, r-1]队列内部 s[j] 单调从小到大每次取队首就是区间最小 s[j] 计算答案。AC代码如下#includebits/stdc.husing namespace std;dequeintdp;intmain(){intn,k;cinnk;vectorlonglongs(n1);s[0]0;for(inti1;in;i){longlongx;cinx;s[i]s[i-1]x;}dp.push_back(0);longlongans-1e18;//极小值初始化for(inti1;in;i){//移除窗口越界下标while(!dp.empty()dp.front()i-k)dp.pop_front();//更新最大段子和ansmax(ans,s[i]-s[dp.front()]);//维护单调递增队列while(!dp.empty()s[i]s[dp.back()])dp.pop_back();dp.push_back(i);}coutansendl;return0;}4力扣 225这道题是使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作比较简单AC代码如下#includequeue using namespace std; class MyStack { private: queueint q1, q2; public: // 入栈直接存入主队列 void push(int x) { q1.push(x); } // 出栈返回栈顶元素 int pop() { // 将q1前n-1个元素转移到q2 while(q1.size() 1) { q2.push(q1.front()); q1.pop(); } // q1.front()就是栈顶 int res q1.front(); q1.pop(); // 把q2元素倒回q1 while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } return res; } // 获取栈顶不删除 int top() { while(q1.size() 1) { q2.push(q1.front()); q1.pop(); } int res q1.front(); q2.push(res); // 栈顶元素不能丢先存入q2 q1.pop(); // 倒回q1 while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } return res; } bool empty() { return q1.empty(); } };分享到这里就结束了
queue函数的应用
发布时间：2026/7/26 7:06:03
一.概况queue函数今天主要学习了STL函数中的queue函数如何使用我在之前的博客中已经写过,在这里请点击下面让我们来看具体题目二.题目来源洛谷 P1886 P1714 P2058力扣 225牛客 NC50528三.题目具体分析1洛谷P1886 牛客[NC50528]这两道题一模一样这道题是一道标准的滑动窗口题运用队列只能在一段插入和在另一端删除从而获得窗口的最大值和最小值AC代码如下#includebits/stdc.h using namespace std; #define int long long signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,k; cinnk; int a[n1]; for(int i1;in;i)cina[i]; dequeintq; //求最小值 for(int i1;in;i){ //当前元素比队尾元素小删除队尾元素 while(!q.empty()a[i]a[q.back()])q.pop_back(); q.push_back(i);//入队 while(q.front()i-k)q.pop_front();//缩小滑动窗口确保窗口大小不超过k if(ik)couta[q.front()] ;//此时队首就是当前窗口最小值 } coutendl; q.clear();//清除 //求最大值 for(int i1;in;i){ //当前元素比队尾元素大删除队尾元素 while(!q.empty()a[i]a[q.back()])q.pop_back(); q.push_back(i);//入队 while(q.front()i-k)q.pop_front(); if(ik)couta[q.front()] ;//此时队首就是当前窗口最大值 } coutendl; return 0; }这道题相对好理解可以当做一个固定的滑动窗口模版来用。2洛谷P2058 海港核心条件输入的船只到达时间 t 严格递增关键天然满足滑动窗口单调性需求处理第 i 艘船时统计区间 (t - 86400 ,t] 所有乘客里不同国籍总数队列queue保存每一位乘客的 (到达时间t国籍x) 按到达先后排队计数数组/桶 cnt[] cnt[x] 当前窗口内国籍 x 的人数变量ans记录当前窗口不同国籍数量。完整流程每一艘船处理步骤读入当前船时间 t 、乘客数量 k 和所有乘客国籍将船上所有乘客 (t, x) 逐个压入队列如果 cnt[x]0 说明窗口新增国籍 ans cnt[x] 清理过期乘客窗口左端弹出循环判断队首乘客时间 q.front().t t - 86400 超出24小时取出队首国籍 x0 cnt[x0]-- 如果 cnt[x0]0 这个国籍没人了 ans-- 队首弹出清理完成后直接输出 ans 。AC代码如下#includebits/stdc.husing namespace std;structnode{intx,t;}h;//定义结构体queuenodeq;//用于储存intans0,num[100005];intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;while(n--){intt,k;cintk;for(inti0;ik;i){intx;cinx;num[x];q.push({x,t});//入队if(num[x]1)ans;//出现新的国家总数加1}//清理过期记录滑动窗口核心for(hq.front();q.size()t-h.t86400;q.pop(),hq.front()){num[h.x]--;if(num[h.x]0)ans--;}coutansendl;}return0;}(3)洛谷P1714 切蛋糕题意给定长度 n 的数组求长度不超过 m 的连续子数组最大和。数据范围 n ≤ 5e5 需要 O(n) / O(n log n) 算法暴力枚举会超时。核心思路预处理前缀和数组 s s[0]0s[i] p₁p₂…pᵢ区间 [l,r] 和 s[r] - s[l-1]约束子数组长度 r-l1 ≤ m ⇒ l-1 ≥ r-m 。对固定右端点 r我们要找 r-m ≤ j ≤ r-1 范围内最小的 s[j]使得 s[r]-s[j] 最大。使用单调递增队列滑动窗口最小值维护队列保存 j 下标满足下标在区间 [r-m, r-1]队列内部 s[j] 单调从小到大每次取队首就是区间最小 s[j] 计算答案。AC代码如下#includebits/stdc.husing namespace std;dequeintdp;intmain(){intn,k;cinnk;vectorlonglongs(n1);s[0]0;for(inti1;in;i){longlongx;cinx;s[i]s[i-1]x;}dp.push_back(0);longlongans-1e18;//极小值初始化for(inti1;in;i){//移除窗口越界下标while(!dp.empty()dp.front()i-k)dp.pop_front();//更新最大段子和ansmax(ans,s[i]-s[dp.front()]);//维护单调递增队列while(!dp.empty()s[i]s[dp.back()])dp.pop_back();dp.push_back(i);}coutansendl;return0;}4力扣 225这道题是使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作比较简单AC代码如下#includequeue using namespace std; class MyStack { private: queueint q1, q2; public: // 入栈直接存入主队列 void push(int x) { q1.push(x); } // 出栈返回栈顶元素 int pop() { // 将q1前n-1个元素转移到q2 while(q1.size() 1) { q2.push(q1.front()); q1.pop(); } // q1.front()就是栈顶 int res q1.front(); q1.pop(); // 把q2元素倒回q1 while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } return res; } // 获取栈顶不删除 int top() { while(q1.size() 1) { q2.push(q1.front()); q1.pop(); } int res q1.front(); q2.push(res); // 栈顶元素不能丢先存入q2 q1.pop(); // 倒回q1 while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } return res; } bool empty() { return q1.empty(); } };分享到这里就结束了
