Your task is to determine the maximum and minimum values in the sliding window at each position. 

8 31 3 -1 -3 5 3 6 7Sample Output
-1 -3 -3 -3 3 3
3 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;}