单调队列题解

题目

有关必回

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N];
deque<int> q;
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && i - q.front() >= k) {
			q.pop_front();
		}
		while (!q.empty() && a[q.back()] >= a[i]) {
			q.pop_back();
		}
		q.push_back(i);
		if (i >= k) {
			cout << a[q.front()] << " ";
		}
	}
	cout << "\n";
	while (!q.empty()) {
		q.pop_front();
	}
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && i - q.front() >= k) {
			q.pop_front();
		}
		while (!q.empty() && a[q.back()] <= a[i]) {
			q.pop_back();
		}
		q.push_back(i);
		if (i >= k) {
			cout << a[q.front()] << " ";
		}
	}
	return 0;
}