题目来源：
https://vjudge.net/contest/292642#problem/G
http://poj.org/problem?id=2823
Description
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.
Input
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.
Output
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.
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
题意：给你一个长度为n的数组和一个区间长度k求数组中1~k,2~k+1,.....n-k~每个区间的最大值和最小值，并且按第一排最小值第二行最大值输出。
思路：单调队列
所谓的单调队列就是一个从头到尾具有严格的单调性的队列，既可以从对尾插入元素，也可以从头尾删除元素。
插入队尾元素：和队尾比较如果大于队尾就队尾出队，继续和队尾比较直到队尾元素大于插入元素就将插入元素入队尾。
删除队首元素：题目给出区间k所以对于每一个i都只要保留它前k-1个元素的最大值，所以当队首元素的i下标小于i-k+1元素的时候删除队首元素。
单调队列参考代码：
#include<cstdio>
using namespace std;
#define N 1000005
int a[N],q[N],n,k;
void git_min()
{
int l=1,r=0,i=0;
for(; i<k-1; i++)
{
while(l<=r&&a[q[r]]>a[i]) r--;
q[++r]=i;
}
for(; i<n; i++)
{
if(q[l]<=i-k) l++;
while(l<=r&&a[q[r]]>a[i]) r--;
q[++r]=i;
printf("%d ",a[q[l]]);
}
printf("\n");
}
void git_max()
{
int l=1,r=0,i=0;
for(; i<k-1; i++)
{
while(l<=r&&a[q[r]]<a[i]) r--;
q[++r]=i;
}
for(; i<n; i++)
{
if(q[l]<=i-k) l++;
while(l<=r&&a[q[r]]<a[i]) r--;
q[++r]=i;
printf("%d ",a[q[l]]);
}
printf("\n");
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
git_min();
git_max();
}
return 0;
} 思路：线段树
线段树建树过程的复杂度为O(n). 采用线段树后总复杂度为O((n-k)logn). 改了下板子尝试了一发C++提交AC，用G++提交TLE，原因未知。（这锅POJ得背
线段树参考代码：
#include<cstdio>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 1000005;
int n, k;
int a[N];
// 线段树节点结构体：区间左端点，区间右端点，区间最大值，区间最小值
struct node
{
int tmax, tmin;
};
node tree[N*4];// 用数组tree模拟完全二叉树
// 线段树函数：build & query &PushUp
//PushUp:根据叶子节点回溯到根节点
void PushUp(int root)
{
tree[root].tmax =max(tree[2*root+1].tmax, tree[2*root+2].tmax);
tree[root].tmin =min(tree[2*root+1].tmin, tree[2*root+2].tmin);
}
// build: 通过数组a递归构造线段树tree
void build(int root, int lp, int rp)
{
if (lp == rp)
{
tree[root].tmax = a[lp];
tree[root].tmin = a[lp];
return;
}
int mid = (lp+rp)/2;
build(2*root+1, lp, mid);
build(2*root+2, mid+1, rp);
PushUp(root);
}
// query: 给定a数组上某个区间(ql,qr)，通过线段树递归(tl,tr)查询区间最大值和最小值
int query(int root, int ql, int qr, int tl, int tr, bool is_max)// is_max 0/1: 查询最小/大值
{
if (ql > tr || qr < tl)
{
if (is_max)
return -inf;
return inf;
}
else if (ql <= tl && qr >= tr)
{
if (is_max)
return tree[root].tmax;
return tree[root].tmin;
}
else
{
int mid = (tl+tr)/2;
if (is_max)
return max(query(2*root+1,ql,qr,tl,mid,1),query(2*root+2,ql,qr,mid+1,tr,1));
return min(query(2*root+1,ql,qr,tl,mid,0),query(2*root+2,ql,qr,mid+1,tr,0));
}
}
int main()
{
while (~scanf("%d%d", &n, &k))
{
for (int i=0; i<n; i++)
scanf("%d", a+i);
build(0, 0, n-1);
for (int i=0; i<=n-k; i++)
printf("%d ", query(0, i, i+k-1, 0, n-1, 0));
printf("\n");
for (int i=0; i<=n-k; i++)
printf("%d ", query(0, i, i+k-1, 0, n-1, 1));
printf("\n");
}
return 0;
} 此题线段树也能过，但是时间却是单调队列的两倍：
优先队列也超时==：（不知道有大佬帮我改改没，，，
#include <cstdio>
#include <queue>
#include <deque>
#define N 1000005
using namespace std;
typedef pair<int, int> ans;
priority_queue<ans> Max;
priority_queue<ans, deque<ans>, greater<ans> > Min;
int min_num[N], max_num[N], a[N];
void print(int *s, int n)
{
for(int i = 0; i < n; i++)
{
if(i) printf(" ");
printf("%d", s[i]);
}
printf("\n");
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i = 0; i < k - 1; i++)
{
scanf("%d", &a[i]);
Max.push(make_pair(a[i], i));
Min.push(make_pair(a[i], i));
}
for(int i = k - 1; i < n; i++)
{
scanf("%d", &a[i]);
Max.push(make_pair(a[i], i));
Min.push(make_pair(a[i], i));
while(Max.top().second < i - k + 1) Max.pop();
while(Min.top().second < i - k + 1) Min.pop();
min_num[i - k + 1] = Min.top().first;
max_num[i - k + 1] = Max.top().first;
}
print(min_num, n - k + 1);
print(max_num, n - k + 1);
return 0;
}
我们琢磨的超时的尺取代码：
#include <iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
#define N 10005
typedef long long ll;
#define mm(a,b) memset(a,b,sizeof(a))
const double pi=acos(-1.0);
ll a[1000005],d[1000005],x[1000005];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0; i<n; i++)
{
scanf("%lld",&a[i]);
}
if(k==1)
{
for(int i=0; i<n; i++)
{
printf("%lld",a[i]);
if(i!=n-1) printf(" ");
}
printf("\n");
for(int i=0; i<n; i++)
{
printf("%lld",a[i]);
if(i!=n-1) printf(" ");
}
printf("\n");
return 0;
}
ll maxx=a[0],minn=a[0];
int bi=0,ei=0,len1=0,len2=0;
for(int i=0; i<k; i++)
{
if(a[i]>maxx)
{
maxx=a[i];
bi=i;
}
if(a[i]<minn)
{
minn=a[i];
ei=i;
}
}
d[len1++]=maxx;
x[len2++]=minn;
for(int i=k; i<n; i++)
{
if(ei==i-k||bi==i-k)
{
maxx=a[i-k+1];
minn=a[i-k+1];
for(int j=i-k+1; j<=i; j++)
{
if(a[j]>maxx)
{
maxx=a[j];
bi=j;
}
if(a[j]<minn)
{
minn=a[j];
ei=j;
}
}
}
else
{
if(maxx<a[i])
{
maxx=a[i];
bi=i;
}
if(minn>a[i])
{
minn=a[i];
ei=i;
}
}
d[len1++]=maxx;
x[len2++]=minn;
}
for(int i=0; i<len1; i++)
{
printf("%lld",x[i]);
if(i!=len1-1) printf(" ");
}
printf("\n");
for(int i=0; i<len2; i++)
{
printf("%lld",d[i]);
if(i!=len2-1) printf(" ");
}
printf("\n");
return 0;
}
京公网安备 11010502036488号