c/c++语言开发共享单调队列

单调队列特点

• 队列中的元素单调
• 运用deque容器实现，保证能在两端操作
• 由于每个元素最多进队一次，出队一次，所以O(1)

单调队列例题

输入输出样例

8 3 1 3 -1 -3 5 3 6 7 

-1 -3 -3 -3 3 3 3 3 5 5 6 7 

OJ
暴力搜索反正是会TLE，考虑单调队列O(n)

#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std;  int n, k, p[1000005]; deque<int>deq;//存放元素在原序列中的下标 int main() { 	ios::sync_with_stdio(false);//和用scanf提速差不多的作用，没用这个就会超时 	cin >> n >> k; 	for (int i = 1; i <= n; i++) { 		cin >> p[i]; 	} 	for (int i = 1; i <= n; i++) { 		while (!deq.empty() && p[deq.back()] > p[i]) {//只要队尾元素大于此时要加入的元素，就pop 			deq.pop_back(); 		} 		deq.push_back(i); 		if (i >= k) {//输出 			while (!deq.empty() && deq.front() <= i - k) {//删除不在此时k区间范围内的元素 				deq.pop_front(); 			} 			cout << p[deq.front()] << " "; 		} 	} 	cout << endl; 	while (!deq.empty()) { 		deq.pop_back(); 	} 	for (int i = 1; i <= n; i++) { 		while (!deq.empty() && p[deq.back()] < p[i]) {//与输出小值一样的思想 			deq.pop_back(); 		} 		deq.push_back(i); 		if (i >= k) { 			while (!deq.empty() && deq.front() <= i - k) { 				deq.pop_front(); 			} 			cout << p[deq.front()] << " "; 		} 	} 	cout << endl; 	return 0; } 

c/c++开发分享单调队列地址：https://blog.csdn.net/weixin_45776185/article/details/107361785