滑动窗口 【模板】单调队列

滑动窗口 /【模板】单调队列
一个比较简单的知识点，现在补充上

#include 
using namespace std;
const int MAX=1e6+5;
int a[MAX];
vector mn;
vector mx;

int main() {
	deque q1;
	deque q2;
	int n,k;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	for (int i=1;i<=n;i++) {
		while (!q1.empty()&&a[q1.back()]>=a[i]) 
			q1.pop_back();
		while (!q1.empty()&&q1.front()+k<=i)
			q1.pop_front();
		q1.push_back(i);
		if (i>=k)
			mn.push_back(a[q1.front()]); 
	}
	
	for (int i=1;i<=n;i++) { 
		while (!q2.empty()&&a[q2.back()]<=a[i]) 
			q2.pop_back();
		while (!q2.empty()&&q2.front()+k<=i) 
			q2.pop_front();
		q2.push_back(i);
		if (i>=k) 
			mx.push_back(a[q2.front()]);
	}
	
	for (int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5715072.html