单调队列 - 滑动窗口

154. 滑动窗口 - AcWing题库

O(1)求窗口中的最大值/最小值

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;

const int N = 1000010;

int a[N], q[N];

int main()
{
	IOS
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i ++)cin >> a[i];
	
	int hh = 0, tt = -1;
	for(int i = 1; i <= n; i ++)
	{
		if(hh <= tt && q[hh] < i - k + 1)hh ++;
		while(hh <= tt && a[q[tt]] >= a[i])tt --;
		q[++ tt] = i;
		if(i >= k)cout << a[q[hh]] << ' ';
	}
	cout << endl;
	
	hh = 0, tt = -1;
	for(int i = 1; i <= n; i ++)
	{
		if(hh <= tt && q[hh] < i - k + 1)hh ++;
		while(hh <= tt && a[q[tt]] <= a[i])tt --;
		q[++ tt] = i;
		if(i >= k)cout << a[q[hh]] << ' ';
	}
	
	return 0;
}