单调的队列
例题：
Poj 2823
给出数列，从左向右输出长度为m的数列各段内的最小数量和最大数量。
数列长度： N=106，m=N
对于单调的队列，这样定义。
1、维护区间最高值
2、如上去除冗馀状态，区间中的两个元素a[i]、a[j] (现在求最大值) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
如果ji且a[j]=a[i]，则a[j]大于a[i]且在后面。 (目前，a[j]留在队列中一定比a[i]更有用。 要说为什么，那是因为你是后起之秀。 核心思想！ ）
3、保持矩阵单调，最大值为单调递减序列，最小值相反
4、最适合团队领导
实现单调队列的大致过程：
1、保护团队领导(对于上述问题，如果团队领导已经在当前要素的m个之前，团队领导应该被删除，head ) )。
2、在队伍末尾插入(每插入一个，先从队伍末尾去除冗馀状态，保持单调性) ) )。
简单示例应用
数列是六四十八六四二十二十四
N=10，K=3；
那么，制作长度为3的单调减少队列。
首先，对其6及其位置0进行排队。 用(6，0 )表示这个。 在每个步骤中插入元素时，队列中的元素如下
插入6 () 6，0 )
4 () 6，0 )，) 4，1 )；
插入10 () 10、2 )
插入第二个10，留下后面的东西。 (10，3 )；
8 () 10、3 )、(8、4 )；
6 () 10、3 )、(8、4 )、(6、5 )；
4、前面的10已经超出范围，所以排除。 (8，4 )、6，5 )、4，6 )；
2、同样，(6、5 )、(4、6 )、(2、7 )；
插入12 (12，8 )；
14 () 14、9 )；
f(I )是步骤I中队列中的第一个元素。 六、六、十、十、十、八、六、十二、十四
同样，最小值也可以在单调队列中进行。
该算法的效率还是很高的，因为单调队列的时间复杂度为o(n )，一个数只能进入入队和出队一次。
注意：建议直接用数组模拟单调的队列。 由于系统附带容器，因此不方便，难以调试。 另外，每个数只能进一次。 因此，排列绝对不会破裂。 空间也是s(n )，优于堆和段树等数据结构。
更重要的是，单调是思想。 在解决问题时，当发现有很多冗馀浪费的状态时，我们可以采用单调的思想，用单调的队列或单调的队列这样的方法消除冗馀状态，保存我们想要的状态。
堆栈
例题：
问题的说明
地上从左向右站着n块板子。 如下图所示，从1到n依次编号。 据了解，每块板的高度，第n块板的右侧立着无限大高度的板。 现在，对各个板依次进行以下操作。 对于第I张板，从右侧注入水，直到水的高度等于第I张板的高度，注入的水淹没第I张板。 (如果板左右两侧的水的高度在板的高度以上，则视为板被水淹没了。 求出n次操作后，所有ai的和是多少。 如上所示，向第4块板的右侧浇水，可以淹没第5块和第6块共计2块板。 a4=2。
用堆栈求解，复杂度为o(n )
组合单调堆栈的性质：使用单调堆栈可以找到元素是向左遍历第一个小于他的元素，还是元素向左遍历第一个大于他的元素。
在寒冷的早晨，单调堆栈是堆栈中元素单调增加或单调减少的堆栈，与单调队列非常相似，但单调堆栈只能在堆栈的顶部操作。
单调堆栈有以下两个性质：
1、单调递增堆栈时，堆栈从顶部到底部的元素会严格增加。 对于单调递减堆栈，从堆栈顶部到底部的元素会严格减少。
2、离堆栈顶部越近的要素越向后进入堆栈。
单调堆栈与单调队列的不同之处在于堆栈只能在堆栈的开头进行操作。 因此，通常在应用单调堆栈的地方，如果不限制堆栈的大小，元素可能无法进入堆栈。
元素堆栈过程：对于单调递增堆栈，如果当前堆栈元素为e，则从堆栈的开头遍历元素，从堆栈中提取e以下或e以下的元素，直接遇到e以上的元素或堆栈直到空，然后将e推入堆栈。 对于单调递减堆栈，每次都会弹出大于e或等于e的元素。
数据模拟板回水单调堆的输入计算过程
想法：找比堆栈顶部高的板子I，找到后拿出堆栈。 否则，将板I放入堆栈中，并给出循环计数样本10、5、8、12、6
从左向右扫描
堆栈为空，10进入堆栈： 10此时堆栈顶部为10，即查找大于10的板
5小于10，5进入堆栈： 5，10此时堆栈顶部为5，也就是找大于5的板子
8大于5，5离开堆栈： 10
此时，在第二个高度为5的板的右侧找到更高的板，为第三个板8，因此5被堆叠，计算为a2=3-2-1=0
8小于10，8进入堆栈： 8，10此时堆栈顶部为8，也就是找大于8的板子
12大于8，8离开堆栈： 10
在第三个高8的板子的右侧发现了比那个高的板子。 第四个板子12、8出来了
栈，计算a3 = 4-3-1 = 012比10大，10出栈 栈：空
第一个高度为10的木板右边比它高的木板已经找到了，是第四个木板12，所以10出栈，计算a1 = 4-1-1 = 2
栈为空，12入栈 栈：12 此时栈顶是12，也就是说要寻找比12大的木板
6比12小，6入栈 栈：6，12 此时栈顶是6，也就是说要寻找比6大的木板
扫描完成结束
最后栈的结构是：6，12 栈顶为6
由于最右端竖立着一块高度无限大的木板，即存在第六块木板高度为无穷，所以剩余两块木板的算法如下 a5 = 6-5-1 =0
a4 = 6-4-1 = 1
sum = a1 + a2 +a3 +a4 +a5 = 3
因此本题可以在O(n)O(n)的时间内迎刃而解了。
从左往右将木板节点压栈，遇到比栈顶木板高的木板就将当前栈顶木板出栈并计算淹没的木板数，如此循环直到栈顶木板高度比当前木板高或者栈为空，然后将此木板压栈。木板全都压栈完成后，栈内剩余的木板都是右侧没有比它们更高的木板的，所以一个个出栈并计算ai=n+1-temp_id-1(用最右边无限高的木板减)。