点击打开链接 题目链接
| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 40565 | Accepted: 11982 | |
| Case Time Limit: 5000MS | ||
Description
| 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
Output
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
用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最小值最大值。
单调队列定义：
a)从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增），比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。
b)从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int que[1111111],num[1111111],maxn[1111111],minn[1111111],index[1111111];
int n,k;
void getmin()
{
int fr=1,ed=0,i;
for(i=0;i<k-1;i++)
{
while(fr<=ed&&que[ed]>=num[i])
ed--;
que[++ed]=num[i];
index[ed]=i;
}
for(;i<n;i++)
{
while(fr<=ed&&que[ed]>=num[i])
ed--;
que[++ed]=num[i];
index[ed]=i;
while(index[fr]<i-k+1)
{
fr++;
}
minn[i-k+1]=que[fr];
}
}
void getmax()
{
int fr=1,ed=0,i;
for(i=0;i<k-1;i++)
{
while(fr<=ed&&que[ed]<=num[i])
ed--;
que[++ed]=num[i];
index[ed]=i;
}
for(;i<n;i++)
{
while(fr<=ed&&que[ed]<=num[i])
ed--;
que[++ed]=num[i];
index[ed]=i;
while(index[fr]<i-k+1)
{
fr++;
}
maxn[i-k+1]=que[fr];
}
}
int main()
{
//freopen("acm.txt","r",stdin);
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
}
getmin();
getmax();
for(int i=0;i<n-k+1;i++)
{
if(i<n-k)
printf("%d ",minn[i]);
else
printf("%d\n",minn[i]);
}
for(int i=0;i<n-k+1;i++)
{
if(i<n-k)
printf("%d ",maxn[i]);
else
printf("%d\n",maxn[i]);
}
return 0;
}
原文：http://blog.csdn.net/qq_16843991/article/details/41551829