本文共 1592 字，大约阅读时间需要 5 分钟。

题目描述

输入格式

输出格式

输入输出样例

8 31 3 -1 -3 5 3 6 7

输出 #1

-1 -3 -3 -3 3 33 3 5 5 6 7

说明/提示

题意：求出移动的、固定长度的滑动窗口中的最大值序列和最小值序列。

思路：完全套用单调队列的模板，写一个单调递增队列和一个单调递减队列即可，注意：数据数组和队列数组都从 1 开始。代码如下：

#include 
   
    using namespace std;const int maxn = 1e6 + 10;int arr[maxn];int qinc[maxn], finc = 1, rinc = 0;int qdec[maxn], fdec = 1, rdec = 0;int posinc[maxn], posdec[maxn];int minArr[maxn], mincnt = 0;int maxArr[maxn], maxcnt = 0;int main() {
   	int n, k;	scanf("%d%d", &n, &k);	//从1开始 	for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);	for (int i = 1; i <= n; ++i) {
   		//单调递增队列非空时 		while (finc <= rinc && arr[i] > qinc[rinc]) --rinc;		qinc[++rinc] = arr[i]; 		posinc[rinc] = i;		if (posinc[finc] + k <= i) ++finc; //队首元素超出区间, 出队		if (i >= k) maxArr[maxcnt++] = qinc[finc];		//单调递减队列非空时 		while (fdec <= rdec && arr[i] < qdec[rdec]) --rdec;		qdec[++rdec] = arr[i];		posdec[rdec] = i;		if (posdec[fdec] + k <= i) ++fdec; //队首元素超出区间, 出队		if (i >= k) minArr[mincnt++] = qdec[fdec]; 	} 	for (int i = 0; i < mincnt; ++i) 		printf(" %d" + (!i), minArr[i]);	printf("\n");	for (int i = 0; i < maxcnt; ++i) 		printf(" %d" + (!i), maxArr[i]);     return 0;}
   

提交AC：

转载地址：https://memcpy0.blog.csdn.net/article/details/108271651 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！