NC51001 Sliding Window 滑动窗口最大最小值问题 堆优化

链接：https://ac.nowcoder.com/acm/problem/51001
来源：牛客网

题目描述
An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 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
Your task is to determine the maximum and minimum values in the sliding window at each position.

输入描述:

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

输出描述:

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

示例1
输入
复制

8 3
1 3 -1 -3 5 3 6 7

输出
复制

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

经典问题,滑动窗口的最值问题,

• 堆优化 $O\left(nlogn\right)$O(nlogn)
• 结构体保存数字的下标和数字本身

struct Node {
	int id, val; //下标和值
	bool operator < (const Node& no) const {
		return val < no.val;
	}
	bool operator > (const Node& no) const {
		return val > no.val;
	}
} ;

• 用两个堆来模拟窗口(一个大根堆，一个小根堆)

std::priority_queue<Node> q1; //大根堆
std::priority_queue<Node, vector<Node>, greater<Node> > q2;

• 初始化窗口内有 $M-1$M−1个元素

for(int i=1; i<m; i++) //初始化窗口里有m-1个元素
   	q1.push({i, a[i]}), q2.push({i, a[i]});

• 每次加入一个元素 $a\left[i\right]$a[i],就把堆内不在窗口区间 $[i-M+1,i]$[i−M+1,i]内的弹出

for(int i=m; i<=n; i++) {
	q2.push({i, a[i]}); //每次加入一个元素
	while(tb.id <= i-m) q2.pop(); //并把所有下标小于窗口左端的值弹走
	printf("%d%c", tb.val, i==n?'\n':' '); //此时堆顶一定是最小值
}

完整代码如下

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e6+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif

#define ta (q1.top())
#define tb (q2.top())

int n, m, Q, K, a[MAXN];
struct Node {
	int id, val;
	bool operator < (const Node& no) const {
		return val < no.val;
	}
	bool operator > (const Node& no) const {
		return val > no.val;
	}
} ;

std::priority_queue<Node> q1; //大根堆
std::priority_queue<Node, vector<Node>, greater<Node> > q2;

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(n), read(m);
	for(int i=1; i<=n; i++) read(a[i]);
	for(int i=1; i<m; i++) //初始化窗口里有m-1个元素
		q1.push({i, a[i]}), q2.push({i, a[i]});

	for(int i=m; i<=n; i++) {
		q2.push({i, a[i]}); //每次加入一个元素
		while(tb.id <= i-m) q2.pop(); //并把所有下标小于窗口左端的值弹走
		printf("%d%c", tb.val, i==n?'\n':' '); //此时堆顶一定是最小值
	}
	for(int i=m; i<=n; i++) {
		q1.push({i, a[i]});
		while(ta.id <= i-m) q1.pop();
		printf("%d%c", ta.val, i==n?'\n':' ');
	}





#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}