## Sliding Window

Time Limit: 12000MS Memory Limit: 65536K
Case Time Limit: 5000MS

### 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```

### Source

`POJ Monthly--2006.04.28, Ikki`

1. 建树( O(n) )
2. 查询最值( O(logn) )
3. 动态更新 ( O(logn) )

1. 仅当i=1时,节点i为根节点.
2. 当i>1时,其父节点为floor(i/2) (对i/2向下取整).
3. 节点i的左右儿子节点分别为2i，2i+1.
4. 当i为奇数且不为1时其左兄弟节点为i-1.
5. 当i为偶数，节点i的右兄弟节点为i+1.

``` t=n*2; for(i=t-2;i>0;i-=2){ j=i+1;x=i>>1; D[x]=D[i]<d[j]?D[i]:D[j]; }```

``` i=l;j=r;x=i; while(i<=j){ if(D[x]>D[i]) x=i; if(D[x]>D[j]) x=j; if(i%2==1) ++i; if(j%2==0) --j; i=i>>1;j=j>>1; }//奇偶缩进的方法```
```int tMin(int l,int r) { if(l==r) return D[l]; if(r==(l+1)) return (D[l]<=D[r]?D[l]:D[r]); int t1=0;t2=0;ll=l;rr=r; if(ll%2==1){ t1=ll; ++ll; }   if(rr%2==0){ t2=rr; --rr; } int ans=tMin(D,ll>>1,(rr-1)>>1); if(t1) ans=D[t1]<=ans?D[t1]:ans; if(t2) ans=D[t2]<=ans?D[t2]:ans; return ans; }//递归方式查询```

CODE 1

```#include<stdio.h> int D[2000000];   int main() { int i,j,k,t,n,x; while(scanf("%d%d",&n,&k)!=EOF){ t=2*n; for(i=n;i<t;++i) scanf("%d",D+i);//获取元素   for(i=t-2;i>0;i-=2){ j=i+1; D[i/2]=D[i]<d[j]?D[i]:D[j];//建最小胜者树 } int l=n,r=n+k-1; while(r<t){ i=l;j=r;x=i; while(i<=j){ if(D[x]>D[i]) x=i; if(D[x]>D[j]) x=j; if(i%2==1) ++i;//奇偶缩进 if(j%2==0) --j; i=i>>1;j=j>>1;//右移一位，相当于i=i/2 } printf("%d ",D[x]); ++l;++r; } putchar('n');   for(i=t-2;i>0;i-=2){ j=i+1; D[i/2]=D[i]>D[j]?D[i]:D[j];//建最大胜者树 } l=n;r=n+k-1; while(r<t){ i=l;j=r;x=i; while(i<=j){ if(D[x]<d[i]) x=i; if(D[x]<d[j]) x=j; if(i%2==1) ++i; if(j%2==0) --j;//奇偶缩进 i=i>>1;j=j>>1; } printf("%d ",D[x]); ++l;++r; } putchar('n'); } return 0; }```

CODE 2(使用递归)

```#include<stdio.h>   int D[2000010]; int tMin(int l,int r) { if(l==r) return D[l]; if(r==(l+1)) return (D[l]<=D[r]?D[l]:D[r]); int t1=0,t2=0,ll=l,rr=r; if(ll%2==1){ t1=ll; ++ll; }   if(rr%2==0){ t2=rr; --rr; } int ans=tMin(ll>>1,(rr-1)>>1); if(t1) ans=D[t1]<=ans?D[t1]:ans; if(t2) ans=D[t2]<=ans?D[t2]:ans; return ans; }   int tMax(int l,int r) { if(l==r) return D[l]; if(r==(l+1)) return (D[l]>=D[r]?D[l]:D[r]); int t1=0,t2=0,ll=l,rr=r; if(ll%2==1){ t1=ll; ++ll; }   if(rr%2==0){ t2=rr; --rr; } int ans=tMax(ll>>1,(rr-1)>>1); if(t1) ans=D[t1]>=ans?D[t1]:ans; if(t2) ans=D[t2]>=ans?D[t2]:ans; return ans; }   int main() { int i,j,k,t,n,x; while(scanf("%d%d",&n,&k)!=EOF) { t=2*n; for(i=n;i<t;i++) scanf("%d",D+i);   for(i=t-2;i>=2;i-=2){ j=i+1;x=i>>1; D[x]=D[i]<=D[j]?D[i]:D[j]; }   int l=n,r=n+k-1; if(r<t) printf("%d",tMin(l,r)); ++l;++r; while(r<t){ printf(" %d",tMin(l,r)); ++l;++r; } putchar('n');   for(i=t-2;i>=2;i-=2){ j=i+1;x=i>>1; D[x]=D[i]>=D[j]?D[i]:D[j]; } l=n;r=n+k-1; if(r<t) printf("%d",tMax(l,r)); ++l;++r; while(r<t){ printf(" %d",tMax(l,r)); ++l;++r; } putchar('n'); } return 0; }```

» 本博客采用署名 2.5 中国大陆许可协议进行许可，本文版权归作者所有，欢迎转载，但必须在明显位置给出原文连接。
anyShare分享到：