luo1428-----区间最小最大值 题解

题目

区间最小最大值

题目描述

给定n个元素，以及一个正整数w，求每段区间的最小最大值。这些区间为：[1,1+w-1], [2,2+w-1], …, [n-w+1,n]。

例如8个元素为[1 3 -1 -3 5 3 6 7], w为3，那么有下列最小最大值：

区间	最小值	最大值
[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

输入

第一行输入n,w

第二行输入n个整数

输出

第一行输出区间最小值

第二行输出区间最大值

样例

输入

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

输出

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

提示

1<=n<=10^6 1<=w<=n

10^-9 <= 元素 <= 10^9

补充

时间限制 2 秒
内存限制 128 MB
来源 luo’s OJ

题解

求最小值：
构建一个单调递增序列，即单调队列，队首是最小值，队尾是最大值
队首是当前区间的最小值，但随着区间的右移动，队首优先会失效并弹出
队尾维护单调队列，如果新增元素小于队尾元素，则队尾元素弹出，
直到队尾元素小于新增元素或队列为空，这样保证队列中的元素是单调递增的

code：

#include <bits/stdc++.h>
using namespace std;
int n,w,a[1000010];
deque<int> q;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d",&n,&w);
	for (int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
	}
	for (int i = 1; i <= n; i++){
		while (!q.empty() && q.front() <= i-w){
			q.pop_front();
		}
		while (!q.empty() && a[q.back()] >= a[i]){
			q.pop_back();
		}
		q.push_back(i);
		if (i >= w){
			printf("%d ",a[q.front()]);
		}
	}
	q.clear();
	printf("\n");
	for (int i = 1; i <= n; i++){
		while (!q.empty() && q.front() <= i-w){
			q.pop_front();
		}
		while (!q.empty() && a[q.back()] <= a[i]){
			q.pop_back();
		}
		q.push_back(i);
		if (i >= w){
			printf("%d ",a[q.front()]);
		}
	}
	printf("\n");
	return 0;
}

测评结果 通过
分数 100
耗时 174 MS
内存 6088 KB
语言 C++
代码长度 788 bytes