滑动窗口区间最大最小值模板

思路

可以定义两个数组，来模拟双端队列，一个用来存储数列，另一个用于存储最值的下标，当新进来窗口数值时，与数组的最值比较，如果新进来的数值大就更新数组最值

代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[1000010], b[1000010], n, k, hh = 0, tt = -1;

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++) {
		if (hh <= tt && b[hh] < i - k + 1)
			hh++;//判断最小值是否还在滑动窗口中，不在就推出元素
		while (hh <= tt && a[b[tt]] >= a[i])
			tt--;//当队尾元素对应a[]中的元素比滑动窗口的最后一个元素大，推出
		b[++tt] = i;
		if (i - k + 1 >= 0)
			cout << a[b[hh]] << " ";
	}
	cout << endl;
	hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		if (hh <= tt && b[hh] < i - k + 1)
			hh++;//判断最小值是否还在滑动窗口中
		while (hh <= tt && a[b[tt]] <= a[i])
			tt--;//队头放最大的元素下标
		b[++tt] = i;
		if (i - k + 1 >= 0)
			cout << a[b[hh]] << " ";
	}
	return 0;
}