| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 41264 | Accepted: 12229 | |
| 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
我按照自己的思路进行了部分优化模拟，仍然超时。
代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <deque>
using namespace std;
struct node
{
int mi;
int ma;
}q[1000004];
int a[1000004];
int main()
{
int n, k;
int i, j;
scanf("%d %d", &n, &k);
for(int i=0; i<n; i++)
scanf("%d", &a[i] );
int dd=a[0], ff=a[0];
for(i=1; i<k; i++)
{
if(a[i]>dd) dd=a[i]; //max
if(a[i]<ff) ff=a[i]; //min
}
int e=0;
q[e].ma=dd; q[e++].mi=ff;
int pos;
for(j=k; j<n; j++ )// 遍历这些序列
{
if(a[j]>dd) dd=a[j];
if(a[j]<ff) ff=a[j]; //判断是不是要更新
pos=j-k;
if(a[pos]>dd && a[pos]<ff )
continue;
else
{
int p, w;
if(a[pos]==dd) //起点是==最大值 更新最大值
{
p=a[pos+1];
for(i=pos+2; i<=j; i++)
{
p=max(p, a[i]);
}
dd=p;
}
else if(a[pos]==ff) //起点是==最小值 更新最小值
{
w=a[pos+1];
for(i=pos+2; i<=j; i++)
{
w=min(w, a[i]);
}
ff=w;
}
q[e].ma=dd; q[e++].mi=ff;
}
}
for(i=0; i<e; i++)
{
if(i==e-1)
printf("%d\n", q[i].mi);
else
printf("%d ", q[i].mi);
}
for(i=0; i<e; i++)
{
if(i==e-1)
printf("%d\n", q[i].ma );
else
printf("%d ", q[i].ma );
}
return 0;
}
POJ 2823 Sliding Window （滑动窗口的最值问题 ）
原文：http://www.cnblogs.com/yspworld/p/4260323.html