单调栈

单调栈

性质

单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。

模型
例如下图就是一个单调递增的单调栈。

其中的元素从小到大排列。

那么，如果我们要加入一个新的元素5，5>4，符合要求，就可以直接加入。

那么如果我们需要加入一个元素3呢？

为了维护单调栈的单调性，我们需要把从栈顶开始，大于3的元素全部弹出，再加入元素3。

如图，我们弹出了4,5。

然后再加入3。

这就是单调栈的基本操作。

其实实现起来很简单：这里以递增的单调栈为例子

如果a[i]<stack.top()  那么 stack.push(a[i])

如果a[i]>stack.top()  那么我们就将所以小于a[i]的都pop()   a[i]其实就是第一个大于我们pop( ) 的元素的值

单调栈主要用来解决：

找到从左/右遍历第一个比它小/大的元素的位置

可能还会有其他的妙用，以后做题做到了再来总结吧