单调栈与单调队列

什么是单调队列

单调队列，即单调递减或单调递增的队列。单调队列与单调栈十分类似， 都是单增单减， 唯一的区别在于弹出元素时， 栈只能在栈顶将后进的元素弹出，而单调队列则可以在队列两端都进行元素的弹出， 在尾部实现元素的插入, 单调队列实际上是应用了双端队列的属性。
举一个形象的例子：假如你在饭堂打饭时，有个人人高马大，急匆匆跑过来，看排了这么一长串队，心中急躁，从队列最后的一个人开始，看见好欺负的就赶走，自己站着，直到干不过的就停下，这就是双端队列。也就是允许两端弹出，只允许一端插入的队列。

图中，企图插队的人战斗力为 6 ，队尾的 5，1 都小于它，而 6 和它战斗力相同，它凭着插队的一股劲，把这三个人全部挤掉，到了 7 的后面。
这就是所谓的单调队列了，队列元素保持单调递增（减），而保持的方式就是通过插队，把队尾破坏了单调性的数全部挤掉，从而使队列元素保持单调。
单调队列的出现可以简化问题，队首元素便是最大（小）值，这样，选取最大（小）值的复杂度便为 O(1)，由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是 O(1)。

正常思路是对每一个盘子从上往下遍历井，这样复杂度是 O(n^2)，想一下怎么优化。

考虑到一个盘子，如果能过宽的层下面的窄层，那么上面那个宽层肯定能过，所以从上往下的时候决定它能不能过的其实是一个宽度递减的序列，所以先预处理一下井，改为递减，存入单调栈中。然后逆向思考，从最下面的那个宽度开始遍历，复杂度 O(n)。