当前位置： 首页 > news >正文

014.单调队列

news 2026/6/11 0:46:23

区分优先队列

它们都有 O( 1 ) 的最值访问

c++标准库中就有priority_queue(优先队列)

而优先队列需要我们手动实现

优先队列priority_queue

  • 二叉堆
  • O ( logn ) 的插入，删除
  • 维护 全局 动态最值

优先队列

  • 双端队列 / 静态数组
  • O ( 1 ) 的插入、删除
  • 维护 滑动窗口 最值

实现方法

现有一个数组 nums[ ] , 窗口大小为 k ,我们需要获得每个窗口的最大值

leetcode239

静态数组

效率高

vector<int>ans;//存储每个窗口的最大值
int n = nums.size();
int q [ n ] // 存储下标
int h=0,t=-1;//头，尾
for(int i=0;i<(int)nums.size();++i){while(t>=h&&nums[q[t]]<nums[i]){t--;}q[++t]=i;if(i+1>=k){while(t>=h&&i-q[h]+1>k){h++;}ans.push_back(nums[q[h]]);}
}

动态双端队列

更直观？

int n=nums.size();
vector<int>ans;
deque<int>q;
for(int i=0;i<n;i++){while(!q.empty()&&q.back()<nums[i]){q.pop_back();}q.push_back(nums[i]);if(i+1>=k){ans.push_back(q.front());if(nums[i-k+1]==q.front()){q.pop_front();}}
}

以上是最大值,最小值同理

封装

显著慢于静态实现
int q [ n ] , h=0 , t=-1

#include<deque>
#include<cassert>
using namespace std;
template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};

习题

可以使用上面的MonotonicQueue

丑陋地解决一系列区间最值问题

其实是水模板

leetcode 239

code 1 
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int>ans;int n=nums.size();int q[100005];int h=0,t=-1;for(int i=0;i<n;++i){while(h<=t&&nums[q[t]]<nums[i])t--;q[++t]=i;if(i+1>=k){while(h<=t&&q[h]<i-k+1)h++;ans.push_back(nums[q[h]]);}}return ans;}
};
code 2 
class Solution {template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;};
};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int>ans;MonotonicQueue<int>q;for(int i=0;i<(int)nums.size();++i){q.push(nums[i]);if(i+1>=k){ans.push_back(q.max());q.pop();}}return ans;}
};

leetcode 1438

code 1 
class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {int n=nums.size();vector<int>q1(100005),q2(100005);int h1=0,t1=-1,h2=0,t2=-1;int l=0,r=0,ans=0;while(r<n){while(t1>=h1&&nums[q1[t1]]<nums[r])t1--;q1[++t1]=r;while(t2>=h2&&nums[q2[t2]]>nums[r])t2--;q2[++t2]=r;r++;while(h1<=t1&&q1[h1]<l)h1++;while(h2<=t2&&q2[h2]<l)h2++;while(l<r&&nums[q1[h1]]-nums[q2[h2]]>limit){l++;while(h1<=t1&&q1[h1]<l)h1++;while(h2<=t2&&q2[h2]<l)h2++;}if(r-l>ans)ans=r-l;}return ans;}
};
code 2 
class Solution {template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
public:int longestSubarray(vector<int>& nums, int limit) {int n=nums.size();MonotonicQueue<int>q;int ans=0;for(int i=0;i<n;i++){q.push(nums[i]);while(!q.empty()&&q.max()-q.min()>limit)q.pop();ans=max(ans,q.size());}return ans;}
};

leetcode 862

code 2 
class Solution {template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
public:int shortestSubarray(vector<int>& nums, int k) {int n=nums.size();vector<long>pre(n+1,0);for(int i=0;i<n;++i)pre[i+1]=pre[i]+nums[i];MonotonicQueue<long>window;int l=0,r=0;int ans=INT_MAX;while(r<=n){window.push(pre[r++]);while(r<=n&&!window.empty()&&pre[r]-window.min()>=k){ans=min(ans,r-l);window.pop();l++;}}return ans==INT_MAX?-1:ans;}
};

leetcode 1696

code 1 
class Solution {
public:int maxResult(vector<int>& nums, int k) {int n=nums.size();vector<int>q(n);int h=0,t=-1;vector<int>dp(n);dp[0]=nums[0];q[++t]=0;for(int i=1;i<n;++i){while(t>=h&&i-q[h]>k)h++;dp[i]=nums[i]+dp[q[h]];while(t>=h&&dp[q[t]]<dp[i])t--;q[++t]=i;}return dp[n-1];}
};
code 2 
class Solution {template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
public:int maxResult(vector<int>& nums, int k) {int n=nums.size();vector<int>dp(n);dp[0]=nums[0];MonotonicQueue<int>q;q.push(dp[0]);for(int i=1;i<n;++i){dp[i]=nums[i]+q.max();if(q.size()>=k)q.pop();q.push(dp[i]);}return dp[n-1];}
};

leetcode 1425

code 1 
class Solution {
public:int constrainedSubsetSum(vector<int>& nums, int k) {int n=nums.size();vector<int>q(n);int h=0,t=-1;vector<int>dp(n);dp[0]=nums[0];q[++t]=0;for(int i=1;i<n;i++){while(t>=h&&i-q[h]>k)h++;dp[i]=max(nums[i],dp[q[h]]+nums[i]);while(t>=h&&dp[q[t]]<dp[i])t--;q[++t]=i;}int ans=dp[0];for(int x:dp)if(x>ans)ans=x;return ans;}
};
code 2 
class Solution {template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
public:int constrainedSubsetSum(vector<int>& nums, int k) {int n=nums.size();vector<int>dp(n);dp[0]=nums[0];MonotonicQueue<int>q;q.push(dp[0]);for(int i=1;i<n;i++){dp[i]=max(nums[i],q.max()+nums[i]);if(q.size()>=k)q.pop();q.push(dp[i]);}int ans=dp[0];for(int x:dp)if(x>ans)ans=x;return ans;}
};

luogu P1886

code 
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>void read(T&x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}if(f)x=-x;}void read(char&c){c=getchar();while(isspace(c))c=getchar();}void read(string&s){s.clear();char ch=getchar();while(isspace(ch))ch=getchar();while(!isspace(ch)&&ch!=EOF){s+=ch;ch=getchar();}}template<typename T,typename...Args>void read(T&first,Args&...rest){read(first);read(rest...);}template<typename T>void wr(T x){if(x==0){putchar('0');return;}if(x<0){putchar('-');x=-x;}char stk[20];int top=0;while(x){stk[++top]=x%10+'0';x/=10;}while(top){putchar(stk[top--]);}}void wr(const char c){putchar(c);}void wr(const string&s){for(char c:s)putchar(c);}void wr(const char*s){while(*s)putchar(*s++);}template<typename T>void wr(const T&x,char sep){wr(x);putchar(sep);}template<typename T,typename...Args>void wr(const T&first,const Args&...rest){wr(first);((putchar(' '),wr(rest)),...);}}using namespace IO;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
void solve(){int n,k;read(n,k);MonotonicQueue<int>q;vector<int>a(n),m,M;for(int i=0;i<n;++i)read(a[i]);for(int i=0;i<n;++i){q.push(a[i]);if(i+1>=k){m.push_back(q.min());M.push_back(q.max());q.pop();}}int siz=m.size();for(int i=0;i<siz;i++){wr(m[i]);if(i==siz-1)wr('\n');else wr(' ');}for(int i=0;i<siz;i++){wr(M[i]);if(i==siz-1)wr('\n');else wr(' ');}
}
int main(){int T=1;//read(T);while(T--){solve();}
}

luogu P2032

code 
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>void read(T&x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}if(f)x=-x;}void read(char&c){c=getchar();while(isspace(c))c=getchar();}void read(string&s){s.clear();char ch=getchar();while(isspace(ch))ch=getchar();while(!isspace(ch)&&ch!=EOF){s+=ch;ch=getchar();}}template<typename T,typename...Args>void read(T&first,Args&...rest){read(first);read(rest...);}template<typename T>void wr(T x){if(x==0){putchar('0');return;}if(x<0){putchar('-');x=-x;}char stk[20];int top=0;while(x){stk[++top]=x%10+'0';x/=10;}while(top){putchar(stk[top--]);}}void wr(const char c){putchar(c);}void wr(const string&s){for(char c:s)putchar(c);}void wr(const char*s){while(*s)putchar(*s++);}template<typename T>void wr(const T&x,char sep){wr(x);putchar(sep);}template<typename T,typename...Args>void wr(const T&first,const Args&...rest){wr(first);((putchar(' '),wr(rest)),...);}}using namespace IO;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
void solve(){int n,k;read(n,k);MonotonicQueue<ll>q;vector<ll>a(n);for(int i=0;i<n;++i)read(a[i]);for(int i=0;i<n;++i){q.push(a[i]);if(i+1>=k){wr(q.max(),'\n');q.pop();}}
}
int main(){int T=1;//read(T);while(T--){solve();}
}

luogu P2251

code 
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>void read(T&x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}if(f)x=-x;}void read(char&c){c=getchar();while(isspace(c))c=getchar();}void read(string&s){s.clear();char ch=getchar();while(isspace(ch))ch=getchar();while(!isspace(ch)&&ch!=EOF){s+=ch;ch=getchar();}}template<typename T,typename...Args>void read(T&first,Args&...rest){read(first);read(rest...);}template<typename T>void wr(T x){if(x==0){putchar('0');return;}if(x<0){putchar('-');x=-x;}char stk[20];int top=0;while(x){stk[++top]=x%10+'0';x/=10;}while(top){putchar(stk[top--]);}}void wr(const char c){putchar(c);}void wr(const string&s){for(char c:s)putchar(c);}void wr(const char*s){while(*s)putchar(*s++);}template<typename T>void wr(const T&x,char sep){wr(x);putchar(sep);}template<typename T,typename...Args>void wr(const T&first,const Args&...rest){wr(first);((putchar(' '),wr(rest)),...);}}using namespace IO;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>class MonotonicQueue{deque<T>q,m,M;public:void push(T e){q.push_back(e);while(!m.empty()&&m.back()>e)m.pop_back();m.push_back(e);while(!M.empty()&&M.back()<e)M.pop_back();M.push_back(e);}T max(){return M.front();}T min(){return m.front();}T pop(){T x=q.front();q.pop_front();if(x==m.front())m.pop_front();if(x==M.front())M.pop_front();return x;}int size()const{return q.size();}bool empty()const{return q.size()==0;}
};
void solve(){int n,k;read(n,k);MonotonicQueue<ll>q;vector<ll>a(n);for(int i=0;i<n;++i)read(a[i]);for(int i=0;i<n;++i){q.push(a[i]);if(i+1>=k){wr(q.min(),'\n');q.pop();}}
}
int main(){int T=1;//read(T);while(T--){solve();}
}

bzoj 5424

code 
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define pii pair<int,int>
#define MOD 1000000007
#define INF 0x3f3f3f3f
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int MAXN=100005;
int a[MAXN],s[MAXN];
int f[MAXN],g[MAXN];
pii q[MAXN];
int h,t,cur;
void solve(){int n=read(),m=read();for(int i=1;i<=n;i++)a[i]=read();n++;s[0]=0;for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];f[i]=INF;g[i]=s[i];}f[0]=0;int ans=INF;int cnt=1;for(int j=1;j<=305;j++){h=0,t=1;cur=0;q[++h]={0,0};int Min=INF;for(int i=1;i<=n;i++){while(s[i-1]-s[cur]>m){Min=min(Min,g[cur]-s[cur]);cur++;}int temp=f[i];f[i]=s[i-1]+Min;while(q[h].second<cur)h++;f[i]=min(f[i],q[h].first);while(h<=t&&q[t].first>temp)t--;q[++t]={temp,i};f[i]+=a[i]*cnt;}ans=min(ans,f[n]);memcpy(g,f,sizeof(g));cnt++;}printf("%d\n",ans);
}
signed main(){int Case_num=read();while(Case_num--){solve();}
}
http://www.rkmt.cn/news/122661.html

相关文章：

  • 模型版本失控？气象预测系统中的更新治理策略，资深架构师亲述避坑指南
  • 通达信轻松买卖点副图，源码分享
  • Caffeine vs Guava Cache 深度对比：特性、性能与选型实践
  • 5步轻松掌握Java对象差异比较：从零基础到实战应用
  • 53、Linux系统性能优化与命令行使用指南
  • 26、深入了解GNU Lesser General Public License（LGPL）
  • 基于Spring Boot的校友交流平台
  • 零售连锁门店数字化变革，高效管理系统成关键
  • 狼和羊的故事还在追我
  • 从待机功耗到峰值调度：智能Agent能源管理全流程详解
  • Wireshark静态分析实战指南：Clang-Tidy配置与源码优化深度解析
  • python-flask-django基于数据分析的个性化健康运动饮食管理系统的设计与实现_gy0754sb
  • 巨 椰 云手机离线多开
  • 2025深度测评泰菲拉床垫到底好不好?附靠谱床垫定做厂家清单 - 栗子测评
  • 【redis-day03-缓存三兄弟及解决方案】
  • ROI 实录：引入 AI Agent 后，我们的接口测试维护成本降低了 70%
  • 52、系统性能优化全攻略
  • HTML如何设计JQuery支持大文件上传的批量选择功能？
  • 阿布昔替尼用法用量全解析：成人与青少年适用指南【海得康】
  • 车规级技术破局智慧巡检！诚芯智联渠道峰会解锁第二增长曲线
  • Vim插件管理器VAM：零基础小白也能轻松驾驭的终极神器
  • 2025国际机票怎么查更准？从实时价格、税费透明度分析机票查询平台 - 资讯焦点
  • 为什么顶尖金融机构都在重构Agent审计日志？背后隐藏的4大合规趋势
  • 2025弹簧床垫工厂哪家好?实测弹簧床垫厂家告诉你答案 - 栗子测评
  • Ramile智能工具：5分钟完成软件著作权代码提取的终极解决方案
  • 为什么你的Agent总无法恢复？这4个坑90%的人都踩过
  • IDM使用指南：获取完整功能体验
  • androlua 安卓13 动态申请sd卡权限
  • Clover Bootloader 完全指南：轻松打造多系统启动环境
  • 2025年蜂窝活性炭厂家推荐：技术先进的蜂窝活性炭制造商品牌 - 深度智识库