| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 36469 | Accepted: 10803 | |
| 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
Source
求每一个长度为k的区间的最大值，最小值，把它们都输出来。
与上面的那道很类似，用两个单调队列，一个递增，一个递减，然后从左向右扫描一遍即可。
POJ G++ tle，C++勉强ac，卡时较严重。
代码：
/* ***********************************************
Author :_rabbit
Created Time :2014/5/12 23:07:15
File Name :20.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int a[1001000],que1[1001000],que2[1001000],ans1[1001000],ans2[1000100];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int n,k;
while(~scanf("%d%d",&n,&k)){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int head=1,end=k,front1=0,tail1=0,front2=0,tail2=0;
for(int i=1;i<=k;i++){
while(front1<tail1&&a[que1[tail1-1]]>a[i])tail1--;//递增序列
que1[tail1++]=i;
while(front2<tail2&&a[que2[tail2-1]]<a[i])tail2--;//递减序列
que2[tail2++]=i;
}
ans1[1]=a[que1[front1]];ans2[1]=a[que2[front2]];
for(int i=k+1;i<=n;i++){
head=i-k+1;end=i;
while(front1<tail1&&a[que1[tail1-1]]>a[i])tail1--;
que1[tail1++]=i;
while(que1[front1]<head)front1++;
ans1[i-k+1]=a[que1[front1]];
while(front2<tail2&&a[que2[tail2-1]]<a[i])tail2--;
que2[tail2++]=i;
while(que2[front2]<head)front2++;
ans2[i-k+1]=a[que2[front2]];
}
for(int i=1;i<=n-k+1;i++)printf("%d%c",ans1[i],i==n-k+1?‘\n‘:‘ ‘);
for(int i=1;i<=n-k+1;i++)printf("%d%c",ans2[i],i==n-k+1?‘\n‘:‘ ‘);
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/25660253