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 ( n l o g n ) O(nlogn) 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 M1个元素
for(int i=1; i<m; i++) //初始化窗口里有m-1个元素
   	q1.push({i, a[i]}), q2.push({i, a[i]});
  • 每次加入一个元素 a [ i ] a[i] a[i],就把堆内不在窗口区间 [ i M + 1 , i ] [i-M+1,i] [iM+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;
}




全部评论

相关推荐

06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务