当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 单调队列

单调队列

2020年07月17日  | 移动技术网IT编程  | 我要评论

单调队列特点

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

本文地址：https://blog.csdn.net/weixin_45776185/article/details/107361785

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网