| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 54824 | Accepted: 15777 | |
| 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
/* 第一道单调序列题，纪念 [题目大意] 给定一个长度为n的数列，求长度为k的定长连续子区间｛a1,a2,a3,a4,…,ak-1,ak｝{a2,a3,…,ak,ak+1}……中每个区间的最大值和最小值。 */ #include<cstdio> #include<iostream> #include<cstring> #define N 80050 #define LL long long using namespace std; LL q[N];//记录的是单调队列中元素在a数组中的下标 int n,k,a[N],I[N]; void getMax(){ int head=1,tail=0; for(int i=1;i<k;i++){ while(head<=tail&&a[q[tail]]<=a[i]) tail--; q[++tail]=i; }//现在1到k-1的优先队列先计算出来 for(int i=k;i<=n;i++){ while(head<=tail&&a[q[tail]]<=a[i])tail--; q[++tail]=i; while(q[head]<=i-k)head++; //如果这个数不在当前区间内那么先不取这个数，再向当前区间选 printf("%d ",a[q[head]]); } } void getMin(){ int head=1,tail=0; for(int i=1;i<k;i++){ while(head<=tail&&a[q[tail]]>=a[i]) tail--; q[++tail]=i; }//现在1到k-1的优先队列先计算出来 for(int i=k;i<=n;i++){ while(head<=tail&&a[q[tail]]>=a[i])tail--; q[++tail]=i; while(q[head]<=i-k)head++; //如果这个数不在当前区间内那么先不取这个数，再向当前区间选 printf("%d ",a[q[head]]); } } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&k)!=EOF&&n) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); getMax(); printf("\n"); getMin(); printf("\n"); } return 0; } /* 样例： 6 2 1 3 2 1 5 6 3 3 2 5 6 1 2 1 1 5 */
原文：http://www.cnblogs.com/wuwangchuxin0924/p/5835675.html