T64 滑动窗口 题解

单调队列模版题 大概思路就是 $gmin$ 函数取得窗口左端的位置，$gmax$ 函数取得窗口右端位置。 然后直接输出答案。。。

#include<bits/stdc++.h>
const int MAXN = 1e6 + 7;
using namespace std;
int q[MAXN], a[MAXN];
int n, k;

void gmin() {
	int h = 0, t = -1;
	for (int i = 1; i <= k; i++) {
		while (h <= t && a[q[t]] >= a[i]) {
			t--;
		}
		q[++t] = i;
	}
	for (int i = k; i <= n; i++) {
		while (h <= t && a[q[t]] >= a[i]) {
			t--;
		}
		q[++t] = i;
		while (q[h] <= i - k) {
			h++;
		}

		cout << a[q[h]] << ' ';
	}
}

void gmax() {
	int h = 0, t = -1;
	for (int i = 1; i <= k; i++) {
		while (h <= t && a[q[t]] <= a[i]) {
			t--;
		}
		q[++t] = i;
	}
	for (int i = k; i <= n; i++) {
		while (h <= t && a[q[t]] <= a[i]) {
			t--;
		}
		q[++t] = i;
		while (q[h] <= i - k) {
			h++;
		}
		cout << a[q[h]] << ' ';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	gmin();
	cout << '\n';
	gmax();
	cout << '\n';
	return 0;
  //by hina.
}

你们再抄一个试试呢？