滑动窗口

问题描述

有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动。问在窗口从左往右滑的时候，每次窗口内数的最大值和最小值分别是多少？
例如：数列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3。

Window position	Minimum value	Maximum value
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

Input

输入有两行。第一行两个整数 n 和k分别表示数列的长度和滑动窗口的大小，1 ≤ k ≤ n ≤ 1000000。
第二行有n个整数表示数列。

Output

输出有两行。第一行输出滑动窗口在从左到右的每个位置时，滑动窗口中的最小值。第二行是最大值。

Sample

input: 
8 3
1 3 -1 -3 5 3 6 7
output: 
-1 -3 -3 -3 3 3
3 3 5 5 6 7

Limitation

Time limit		12000 ms
Memory limit	65536 kB

解题思路

维护局部单调性，可以用单调队列。

求最小值可以用单调非减队列，从左往右依次入队，若入队的元素比队尾小则不断弹出队尾元素直到符合条件。当队尾索引 - 队首索引 + 1 = 滑动窗口大小时，队首元素弹出，此时队首元素就是最小值。

同理，求最大值用单调非增队列。

两次遍历就能求出最大最小值。

源代码

#include <deque>
#include <cstdio>
using namespace std;

struct num {//记录元素值与位置
	int a, b;
	num(int x, int y) :a(x), b(y) {  }
};

void getMin(int* arr, int n, int k) {
	deque<num> q;
	for (int i = 0; i != n; i++) {
		while (!q.empty() && q.back().a >= arr[i])
			q.pop_back();//队尾大于要入队的元素
		num x(arr[i], i);
		q.push_back(x);//符合条件 可以入队
		if (i + 1 >= k) {//到达了窗口的宽度  队首弹出
			while (i - q.front().b > k - 1)
				q.pop_front();
			printf("%d ", q.front().a);
		}
	}
}

void getMax(int* arr, int n, int k) {
	deque<num> q;
	for (int i = 0; i != n; i++) {
		while (!q.empty() && q.back().a <= arr[i])
			q.pop_back();//队尾小于要入队的元素
		num x(arr[i], i);
		q.push_back(x);//符合条件 可以入队
		if (i + 1 >= k) {//到达了窗口的宽度  队首弹出
			while (i - q.front().b > k - 1)
				q.pop_front();
			printf("%d ", q.front().a);
		}
	}
}

int main() {
	int n, k;
	scanf_s("%d%d", &n, &k);
	int* arr = new int[n + 10];
	for (int i = 0; i != n; i++)
		scanf_s("%d", &arr[i]);
	getMin(arr, n, k);
	printf("\n");
	getMax(arr, n, k);
	printf("\n");

	return 0;
}