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

单调队列特点队列中的元素单调运用deque容器实现,保证能在两端操作由于每个元素最多进队一次,出队一次,所以O(1)单调队列例题输入输出样例8 31 3 -1 -3 5 3 6 7-1 -3 -3 -3 3 33 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[


单调队列特点

  • 队列中的元素单调
  • 运用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

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/598872.html

(0)
上一篇 2021年5月8日
下一篇 2021年5月8日

精彩推荐