| 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.
InputThe 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. OutputThere 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 Input8 31 3 -1 -3 5 3 6 7Sample Output-1 -3 -3 -3 3 33 3 5 5 6 7
題目大意：給你一個數組，然后讓從左到右，找到每連續k個數的最大值和最小值并且輸出
題目分析：單調隊列解決，然后用C++卡時間AC，用G++會超時
這個問題相當于一個數據流（數列a）在不斷地到來，而數據是不斷過期的，相當于我們只能保存有限的數據（sliding window中的數據，此題中就是窗口的寬度w），對于到來的查詢（此題中查詢是每時刻都有的），我們要返回當前滑動窗口中的最大值/最小值。注意，元素是不斷過期的。
解決這個問題可以使用一種叫做單調隊列的數據結構，它維護這樣一種隊列：
a)從隊頭到隊尾，元素在我們所關注的指標下是遞減的（嚴格遞減，而不是非遞增），比如查詢如果每次問的是窗口內的最小值，那么隊列中元素從左至右就應該遞增，如果每次問的是窗口內的最大值，則應該遞減，依此類推。這是為了保證每次查詢只需要取隊頭元素。
b)從隊頭到隊尾，元素對應的時刻（此題中是該元素在數列a中的下標）是遞增的，但不要求連續，這是為了保證最左面的元素總是最先過期，且每當有新元素來臨的時候一定是插入隊尾。
滿足以上兩點的隊列就是單調隊列，首先，只有第一個元素的序列一定是單調隊列。
那么怎么維護這個單調隊列呢？無非是處理插入和查詢兩個操作。
對于插入，由于性質b，因此來的新元素插入到隊列的最后就能維持b)繼續成立。但是為了維護a)的成立，即元素在我們關注的指標下遞減，從隊尾插入新元素的時候可能要刪除隊尾的一些元素，具體說來就是，找到第一個大于（在所關注指標下）新元素的元素，刪除其后所有元素，并將新元素插于其后。因為所有被刪除的元素都比新元素要小，而且比新元素要舊，因此在以后的任何查詢中都不可能成為答案，所以可以放心刪除。
對于查詢，由于性質b，因此所有該時刻過期的元素一定都集中在隊頭，因此利用查詢的時機刪除隊頭所有過期的元素，在不含過期元素后，隊頭得元素就是查詢的答案（性質a），將其返回即可。
由于每個元素都進隊出隊一次，因此攤銷復雜度為O(n)。
程序實現過程中先將前k個元素入隊，此后每次在隊尾加入a[k+1...n]，在插入元素中同時進行以下操作：
1、將隊尾所有大于a[i]的值彈出隊列
2、插入a[i]到隊尾
3、判斷隊首元素位置是否超出i-k
注意：
1、在更新隊列元素時要同時記錄該元素在原數據的位置
2、在進行操作1時要用二分優化(可以用C++編譯器卡時間AC，但換成G++和GCC就會TLE)
#include <iostream>#include <fstream>#define maxn 1000010using namespace std;int a[maxn],q[maxn],p[maxn],Min[maxn],Max[maxn],n,k;// a是數據，q是隊列，p是存放下標void gmin(){ int tail=0,head=1,i; for(i=0;i<k-1;i++){ while(head<=tail && q[tail]>=a[i])//若添加的元素小于隊尾元素，符合條件，刪除隊尾元素，直到隊尾元素小于此元素為止 --tail; q[++tail]=a[i];//存放滿足條件的數據 p[tail]=i;//記錄存儲的數據下標，保證每個窗口所讀入的數據都在k的范圍內 } for(;i<n;i++){ while(head<=tail && q[tail]>=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; while(p[head]<i-k+1)//利用查看數據是否過時，即是否在窗口內 ++head; Min[i-k+1]=q[head];//存放數據答案 }} void gmax(){ int tail=0,head=1,i; for(i=0;i<k-1;i++){ while(head<=tail && q[tail]<=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; } for(;i<n;i++){ while(head<=tail && q[tail]<=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; while(p[head]<i-k+1) head++; Max[i-k+1]=q[head]; }} void output(){ for(int i=0;i<n-k;i++) PRintf("%d ",Min[i]); printf("%d/n",Min[n-k]); for(int i=0;i<n-k;i++) printf("%d ",Max[i]); printf("%d/n",Max[n-k]);}int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&a[i]); gmin(); gmax(); output(); return 0;}
新聞熱點
疑難解答
