單調遞增或單調減的棧，跟單調佇列差不多，但是只用到它的一端，利用它可以用來解決一些ACM/ICPC和OI的題目，如RQNOJ 的諾諾的佇列等。
單調棧的套用
先看例題：
Loongint的花籃
【Description】
Loongint要和MM結婚了。在兩人的走進禮堂的紅地毯兩側，需要擺一些裝飾用的花籃，有一些不同高度的花籃，現在這些花籃被Loongint依照自己的美學觀念編號為S1,S2,S3…Sn（兩側的花籃高度一樣）。可Loongint的MM對這些花籃的擺放方式有不同的看法，她覺得滿足以下條件的花籃擺放才是最好的。
如果對於區間[Si,Sj](1<=i<j<=n)中任意的花籃都比Si高且比Sj低，那么這個區間稱為一個美學區間。對於所有的美學區間，其長度（定義為j-i）都必須小於等於k，如果有長度大於k的美學區間，MM就會不高興，Loongint就會有麻煩…
【Input】
第一行為m。表示有m組測試數據。
對於每一組：
第一行n，k，分別表示花籃的數量和美學區間的最大長度。
第二行為n個數，分別表示S1,S2,S3…Sn的值。
【Output】
如果根本不存在美學區間，輸出-1。
如果存在美學區間，那么如果任意區間的長度都小於等於k，那么輸出最大的長度，否則輸出最大長度比k大多少（MaxLength-k）。
【Sample Input】
3
4 2
5 4 3 6
4 1
6 5 4 3
4 2
1 2 3 4
【Sample Output】
1
-1
1
【Hint】
對於30%的測試數據，1<=n<=100。
對於60%的測試數據，1=<n<=5555。
對於100%的測試數據，1<=n<=100000，0<Si<=100000，1=<m<=3。
分析
本題的意思是找到一個區間，讓區間的頭元素是最小的尾元素是最小的（中間不能有和首尾相同的元素），即區間的最值是頭和尾，所以很自然可以想到求區間最值的ST算法，但這樣操作有兩個弊端：
1. 必須枚舉區間長度，可能逾時
2. 難以判斷區間裡是否有相同元素
所以ST算法難以勝任，所以我們採用單調棧，顧名思義就是在入棧時遵循單調原則，可以求出一個元素向左（或向右）所能擴展到的最大長度，並不是說在這一段區間內是單調的，而是保證在該區間內該元素一定是最大或最小。因此，對於這道題我們可以求兩次單調棧，以確定兩端點一定滿足題目條件。
不能一直維持棧，使其一開始下降就全部彈出棧，因為在要求的區間內不一定非得是單調
