单调队列

单调队列特点

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