单调栈和单调队列的应用如何构成一个？

单调栈、单调队列及其应用 要补一些东西比如说二维单调队列 另外后面还有单调队列优化dp 单调栈 单调栈并不是一种真正的数据结构，而是一种算法思想 很多题都有用到 单调栈指栈内的元素从栈顶到栈底单调递增/递减 单调栈的插入元素： 假设栈顶到栈底从大到小 先比较栈顶，假设待插入元素大于等于栈顶，就直接入栈 否则就一直出栈直到待插入元素大于等于堆顶，然后停止循环，入栈 出栈很简单，直接弹出栈顶 单调栈的复杂度是\(O(n)\)的，因为虽然每一次插入元素会有弹出操作 但是弹出的元素不会再次入栈，所以如果弹出n个元素，那么之后就不可能弹出了，后面的插入就是\(O(1)\)的 看一道例题 有\(n\)栋楼房横向紧挨着排列，给定每栋楼房的宽度和高度，现在想要用一些矩形海报覆盖住这些楼房，要求必须恰好覆盖，不能多出来或露出楼房，求最少要用的矩形海报的张数 首先一张海报至少覆盖一栋楼房，否则肯定不能最少 即如果海报的高度连最低的楼房都不到，那么就不要这么铺， 所以每铺一张海报就要至少覆盖一栋楼房 再考虑一点，张数与宽度无关，只与高度有关，看上面的样例，最矮的右边可以拉一大张海报，高度是它右边紧接着的那个的高度，宽度只要它刚好覆盖就行，由此可见，海报宽度可以无限延伸，但高度不能超出范围 所以把所有海报想成等宽的即可 第三 假如每栋楼房高度各不相同，那么海报最少要\(n\)张 即横向铺设海报并不能减小张数 由此可见，横向铺设海报虽然下面有共用的部分，但是相当于折算到某一栋楼房上，而上面那些突起的算作另外的一些栋楼房上，还是\(n\)张，红色的想做第\(4\)栋 蓝色的想做第\(2\)栋 绿色\(1\) 浅绿色\(3\) 黄色\(5\) 假如楼房中有一些高度是相同的，且它们之间的楼房高度都\(>=\)它们的高度，那么此时这些相同高度的楼房可以合并，共用一张海报，横向铺设，可以减少张数 假设楼房中有一些高度是相同的，但是它们之间的楼房高度存在\(<\)它们的高度的，那么这些相同高度的楼房不可以合并，不可以横向共用一张海报，因为中间高度有更小的，那样铺设中间不符合要求 所以不能减少张数 然后最少的海报张数就是用n减去可以合并的海报张数 然后再\(+1\) \(7-2+1=6\) 所以为了符合上述条件，我们可以使用单调栈 我们读入时只考虑高度，然后每读入一个，就比较它和栈顶元素高度的关系 当它比栈顶元素高度大或是空栈时，直接将它入栈，因为这时它不可能与前面的元素共用海报，因为前面的元素有一个小于它 而入栈代表它以后可能遇到和它高度相同的以共用海报 当它比栈顶元素高度小或相等时，就有可能与前面的元素共用海报 先循环： 比较它和栈顶元素是否相等，相等就\(ans++\) 代表合并\(1\)次 然后栈顶出栈，因为它比较矮，所以它前面的比它高的元素对后面没有影响 这样可以不断找前面有没有可以合并的楼 当它比栈顶元素大时，栈顶元素比它小，此时前面即使有相等的也无法合并，可以终止循环 终止后将它入栈 这样以后再有可以合并时会继续合并 因为它找相等的时候只找了除去它自己的相等的楼房个数，而合并后至少使用一张海报，所以最终输出\(n-ans\)即可 单调栈的另一个应用是 解决rmq问题 当然是无修改离线的 且这个栈不是真正意义上的栈，而是一个vector \(n\)个数，每个数可正可负，现在有\(m\)组询问，每一次询问区间\([l,r]\)的最大值，不强制在线 首先把所有询问记录在数组b里，用一个结构体记录每一组询问的\(l\) \(r￥ 然后按照\)r\(，从小到大把数组\)b\(排序，\)r\(相等时按l从小到大排序 复杂度\)O(qlogq)\( 然后开一个单调栈，遍历\)a\(数组的所有元素 同时在数组\)b\(拿一个指针记录当前遍历到的待查询的区间 指针先指向开头 然后遍历\)a$，每遍历一个就尝试把元素入栈 注意我们维护栈底最大，而不是栈顶最大 因为栈顶最大难以维护 如 \(3\) \(1\) \(2\) \(3\)入栈 因为\(1<3\) \(3\)出栈 然后\(1\)入栈 然后\(2\)入栈 \(2>1\)，\(1\)不出栈 此时栈顶为\(2\)，而不是\(3\) 不正确 而栈底最大： 3 1 2 \(3\)入栈 \(1<3\) 所以\(1\)入栈 因为\(2>1\) 所以\(1\)出栈 然后\(2<3\) \(3\)不出栈 \(2\)入栈 栈底为\(3\) 正确 当待插入元素大于栈顶元素时，栈顶元素出栈，因为前面这些元素小于待插入元素 若待