題目描述

給你一個長度為N的數(shù)組，一個長為K滑動的窗體從最左移至最右端，你只能見到窗口的K個數(shù)，每次窗體向右移動一位，如下表：

Window position Min value Max value[1 3 -1] -3 5 3 6 7 -1 31 [3 -1 -3] 5 3 6 7 -3 31 3 [-1 -3 5] 3 6 7 -3 51 3 -1 [-3 5 3] 6 7 -3 51 3 -1 -3 [5 3 6] 7 3 61 3 -1 -3 5 [3 6 7] 3 7

你的任務(wù)是找出窗口在各位置時的Max value ，Min value。

輸入格式

第一行n，k，第二行長度為n的數(shù)組

輸出格式

第一行每個位置的Min value，第二行每個位置的Max value

輸入樣例

8 3 1 3 -1 -3 5 3 6 7

輸出樣例

-1 -3 -3 -3 3 3 3 3 5 5 6 7

限制與約定

20%：n≤500；

50%：n≤100000；

100%：n≤1000000；

時間限制：1s

空間限制：128MB

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn = 1000000+10; int a[maxn],ans1[maxn],pos1[maxn],ans2[maxn],pos2[maxn]; int main() {int n,k;cin>>n>>k;for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l1=0,r1=1,l2=0,r2=0;for(int i=1;i<=n;i++){if(i-k+1>pos1[l1]) l1++;while(a[i]<a[ pos1[r1] ] && r1>=l1) r1--;pos1[++r1]=i;ans1[i]=a[pos1[l1]];if(i-k+1>pos2[l2]) l2++;while(a[i]>a[ pos2[r2] ] && r2>=l2) r2--;pos2[++r2]=i;ans2[i]=a[pos2[l2]];}for(int i=k;i<=n;i++) cout<<ans1[i]<<" ";cout<<endl;for(int i=k;i<=n;i++) cout<<ans2[i]<<" ";/* if(a[i]>a[Max[bx]]) {int j;for(j=bx;j>=0;j--){if(a[i]<a[Max[j])break;}bx=j+1;Max[bx]=i;}else Max[++bx]=a[i];if(a[i]<Min[sx]){int j;for(j=sx;j>=0;j--){if(a[i]>Min[j])break;}sx=j+1;Min[sx]=a[i];}else Max[++sx]=a[i];if(i>=k){if(bx-k>0) amax[i]=Max[bx-k];else amax[i]=Max[1];if(sx-k>0) amin[i]=Min[sx-k];else amin[i]=Min[1];}*/return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hfang/p/11239923.html

總結(jié)

以上是生活随笔為你收集整理的窗口单调队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。