#创作计划#单调队列及其模板题

☕

2025-10-07 17:55:56

发布于：四川

8阅读

0回复

0点赞

什么是单调队列

单调队列是一种通过维护元素单调性（递增或递减）来优化算法效率的数据结构，常用于处理滑动窗口最大值/最小值、动态规划等问题。其核心特性包括：

核心特性
◉单调性‌：队列中的元素保持递增或递减排列，例如单调递增队列中元素从队头到队尾逐渐增大，单调递减队列则逐渐减小。 ‌

◉‌高效操作‌：通过维护单调性，每个元素最多进出队列一次，时间复杂度稳定为O(n)。 ‌

典型应用场景
‌◉滑动窗口问题‌：如求每个窗口内的最大值或最小值，通过维护单调递减队列实现高效查询。 ‌
‌
◉动态规划优化‌：在背包问题等场景中，单调队列可将复杂问题转化为简单问题，提升算法效率。 ‌

实现要点
◉‌插入操作‌：从队尾插入元素，若新元素破坏单调性则移除尾部元素。 ‌

◉‌删除操作‌：根据需求从队首或队尾移除元素，保留有效信息。

模板题环节(题目链接:洛谷题目)(题目链接:ACGO题目)

题目介绍

有一个长为 n 的序列 a，以及一个大小为 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 个整数，表示序列 a。

输出格式

输出共两行，第一行为每次窗口滑动的最小值；
第二行为每次窗口滑动的最大值。

输入输出样例

输入#1
8 3
1 3 -1 -3 5 3 6 7
输出 #1
-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示
【数据范围】
对于 50% 的数据，1≤n≤10的5次方；
对于 100% 的数据，1≤k≤n≤10的6次方,a[i]∈[−2的31次方,2的31次方)

//窗口滑动/单调队列模板,附注释
#include<bits/stdc++.h>
using namespace std;
//双向队列 
deque<int>minn,maxn;
int main(){
	int n,k;
	int a[1000086];
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//注:此处单调队列存下标
	 
	//滑动窗口最小值 
	for(int i=1;i<=n;i++){
	//	1.踢出窗口外的元素下标  
		if(!minn.empty()&&minn.front()<i-k+1){
			minn.pop_front();
		}
	//	2.保持队列单调性
	//	  如果新元素a[i]比队尾元素小，那么队尾元素在窗口中永远不为最小值，直接踢出 
		while(!minn.empty()&&a[minn.back()]>=a[i]){
			minn.pop_back();
		}
	//	3.将当前元素下标加入对尾 
		minn.push_back(i);
	//	4.输出结果 
		if(i>=k){
			cout<<a[minn.front()]<<" ";
		}
	}
	cout<<endl;
	//滑动窗口最大值 
	for(int i=1;i<=n;i++){
	//	1.踢出窗口外的元素下标  
		if(!maxn.empty()&&maxn.front()<i-k+1){
			maxn.pop_front();
		}
	//	2.保持队列单调性
	//	  如果新元素a[i]比队尾元素大，那么队尾元素在窗口中永远不为最大值，直接踢出 
		
		while(!maxn.empty()&&a[maxn.back()]<=a[i]){
			maxn.pop_back();
		}
	//	3.将当前元素下标加入对尾 
		maxn.push_back(i);
	//	4.输出结果 
		if(i>=k){
			cout<<a[maxn.front()]<<" ";
		}
	}
	return 0;
}