特殊数据结构模版
2026-08-16 14:36:29
发布于：广东
10阅读
0回复
0点赞
本篇关于单调队列&单调栈
单调栈
stack<int> s;//存下标
for(int i=n;i>=1;i--){//解决前面第一个比a[i]大或小问题就将这个循环改为正序,
while(s.size()&&a[s.top()]<=a[i]) s.pop();//这是解决后面第一个比a[i]大的,如果比a[i]小,
//意味着无法对结果产生影响,出栈删除;
//解决第一个比a[i]小的就把"<"改成">"
s.size()?r[i]=s.top():r[i]=0;//记录答案
s.push(i);
}
单调队列
//求第一个比a[i]小的
deque<int> q;
for(int i=1;i<=n;i++){
while(q.size()&&q.front()<i-k+1) q.pop_front();//在窗口外,没用
while(q.size()&&a[q.back()]>=a[i]) q.pop_back();//从末端开始比,>=它的都没用
q.push_back(i);
if(i>=k) printf("%lld ",a[q.front()]);//长度不是k时不能输出
}
有帮助，赞一个