前置知識：

　　棧

　　隊列

單調棧

　　思考這樣一個問題：給定一個數列，詢問每一個數左邊的第一個比它小的數。

　　暴力的做法是：記錄下所有讀進來的數，然後，每次向前查找，預計時間複雜度O(n²)，而且容易被卡。

　　仔細思考一下，可以發現，這個做法之所以效率低下，是因為每一次都重覆查找了許多肯定不是最優解的元素。很明顯，如果當前查找時這個元素不是最優解，那麼在之後的查找中它也不會是最優解。我們可以用一個棧來維護：每一次把不是最優解的元素出棧，然後把當前的元素加入棧中。由於每個元素最多進棧一次、出棧一次，因此這個演算法的效率是O(n)的。

　　上例中，我們使用的這個棧就是一種簡單的單調棧。單調棧中的元素具有單調性，而為了保證這一點，在元素加入棧中前需要把棧中所有破壞單調性的元素刪除。

　　如果從正反兩個方向各掃一遍單調棧，可以處理出每個元素在哪一段區間中是最小的。

　　放上代碼：

int n,top,a[N],b[N];
//a[N]為原序列，b[N]記錄維護的答案 
struct node{
    int pos,val;
}q[N];
//單調棧：pos記錄在原序列中的位置，val記錄權值 
void work(){
    for(int i=1;i<=n;i++){
        while(top&&q[top].val<a[i]) b[q[top].pos]=i,top--;//維護單調性 
        q[++top].val=a[i];q[top].pos=i;
    }
}

單調隊列

　　單調隊列與單調棧的原理是一樣的。但它還可以通過移動頭指針來及時排除那些已在範圍之外的答案以保證最終答案的正確性。同單調棧一樣，由於每個元素最多入隊一次、出隊一次，單調隊列的效率也是O(n)的。

　　放上代碼：

int n,k,l,r,d[N],a[N],b[N];
//k為指定的區間長
struct node{
    int pos,val;
}q[N];
void work(){
    l=1,r=0;
    for(int i=1;i<=n;i++){
        while(q[l].pos<i-k+1&&l<=r) l++;//先調整隊首指針以排除非法答案
        while(a[i]>=q[r].val&&l<=r) r--;//維護單調性
        q[++r].pos=i;q[r].val=a[i];b[i]=q[l].val;
    }
}