单调递增或单调减的栈，跟单调队列差不多，但是只用到它的一端，利用它可以用来解决一些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算法难以胜任，所以我们采用单调栈，顾名思义就是在入栈时遵循单调原则，可以求出一个元素向左（或向右）所能扩展到的最大长度，并不是说在这一段区间内是单调的，而是保证在该区间内该元素一定是最大或最小。因此，对于这道题我们可以求两次单调栈，以确定两端点一定满足题目条件。

不能一直维持栈，使其一开始下降就全部弹出栈，因为在要求的区间内不一定非得是单调