单调队列代码模板

//单调队列 STL
#include
#include
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
ll a[N];
 
void solve()
{
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; ++i)cin >> a[i];
	deque<int> dq;//存放下标
	//求最大
	for (int i = 1; i <= n; ++i)
	{
		//以i为右端点，大小为k的区间，[i-k+1,i]
		//1.队头合法性
		while (dq.size() && dq.front() <= i - k) dq.pop_front();//<=i-k就是
		//2.队尾优越性
		while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
		dq.push_back(i);
		if (i >= k)cout << a[dq.front()] << " ";
	}
	cout << '\n';
	dq = deque<int>();//清空
	//求最小
	for (int i = 1; i <= n; ++i)
	{
		//以i为右端点，大小为k的区间，[i-k+1,i]
		//1.队头合法性
		while (dq.size() && dq.front() <= i - k) dq.pop_front();
		//2.队尾优越性
		while (dq.size() && a[dq.back()] >= a[i]) dq.pop_back();
		dq.push_back(i);
		if (i >= k)cout << a[dq.front()] << " ";
	}
}
 
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}